Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
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 1

up vote 7 down vote accepted

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.

share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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