# Bipartite graph 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?

• Yuval's answer shows nicely how this is NP-hard. However, for the special case of a complete bipartite graph, your problem can be solved in $O(|V|)$ time. Not sure how helpful this would be to you though. – Paresh Feb 12 '13 at 14:50
• Thanks, but it need not be complete (and rarely, if ever, is). – Paul Reiners Feb 12 '13 at 18:32

## 1 Answer

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.

• I managed to prove the problem NP-hard by reducing from 3-SAT. Your reduction says much more about the difficulty than mine, as set cover is APX-Hard. Nice answer! – rizwanhudda Feb 12 '13 at 14:44
• Thanks! I can see how you reduce a set cover problem to my problem now. Are you also saying that an arbitrary instance of my problem can be reduced to a set cover problem? – Paul Reiners Feb 12 '13 at 18:50