4
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Paresh Feb 12 '13 at 14:50
  • $\begingroup$ Thanks, but it need not be complete (and rarely, if ever, is). $\endgroup$ – Paul Reiners Feb 12 '13 at 18:32
7
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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! $\endgroup$ – rizwanhudda Feb 12 '13 at 14:44
  • $\begingroup$ 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? $\endgroup$ – Paul Reiners Feb 12 '13 at 18:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.