Bipartite graph question

Question

Assume you are given a bipartite graph $G = (U, V, E)$ and you are given an integer $n$. Assume also that for each $v \in V$, you are given two integers $v_{min}$ and $v_{max}$ (where $v_{min} \le v_{max}$).

The problem is to find a subset $U'$ of $U$ of size $n$ such that for each $v \in V$, the number of edges coming into $v$ from $U'$ is between $v_{min}$ and $v_{max}$.

Given a problem like this, can we determine efficiently whether there is a solution? And, if there is a solution, can we find one efficiently?

If we can't do so efficiently, is there an approximation algorithm?

Answer 1

Your problem is NP-hard, by reduction from set cover. Given an instance of set cover with universe $V$, sets $U$ and number $n$, draw an edge between a set and a point if the set contains the point. Let $v_\min = 1$ and $v_\max = |U|$. A subset $U'$ satisfies the $v_\min,v_\max$ constraints iff it is a set cover. So if there is a set cover $W$ of size $m \leq n$, you can complete it to some $U'$ of size $n$ by adding $n-m$ sets and get a solution to your problem. Conversely, any solution to your problem is a set cover of size $n$.

Set cover is also hard to approximate better than $\log n$ (under reasonable assumptions), and this carries over to your problem. Your problem could be much harder.