Possible Duplicate:
Restricted version of vertex cover

Suppose we have a $(A,B,E)$ bipartite graph and a positive integer k. Suppose that k is smaller than $|A|$ and we want to find one of those k element subsets of $A$ which covers the most points from $B$. I can only come up wirh exponential algorithms. Is this in $P$?

Also is mixed integer programming for maximal flows in $P$? It can be easily formulated as such.

  • $\begingroup$ No this problem is NP-Hard. You can do a reduction from Dominating set problem to this one. One Hint is that you have to make $O(\log{|V|})$ calls to your algorithm. Look at my answer to a similar question. $\endgroup$ Commented Jun 22, 2012 at 0:32
  • $\begingroup$ Welcome! The first part of the question is an exact duplicate. I don't know what you are aiming at with the second question; max-flow is in $P$ and has efficient algorithms, no need to go to integer programming. $\endgroup$
    – Raphael
    Commented Jun 22, 2012 at 9:34


Browse other questions tagged or ask your own question.