1
$\begingroup$

I have a question about the Set Cover problem: If I get a universe $U$, and $m$ subsets of size exactly $2$, and an integer $k$. Is this problem is still NP-C or I can solve it on a polynomial time?

Thanks.

$\endgroup$
  • $\begingroup$ There is no explanation there why is it so, and it seems that the author doesn't sure in his answer. $\endgroup$ – Rbix Jul 5 '17 at 12:51
3
$\begingroup$

This is exactly the edge cover problem, which can be solved in polynomial time by finding a maximum matching. Then, for each unmatched vertex, add an arbitrary edge containing that vertex.

In fact, if all you want to know is whether there's an edge cover of size at most $k$, you don't need to construct the cover: the size of a minimum edge cover is $M + n - 2M = n-M$, where $n$ is the number of vertices in the graph and $M$ is the number of edges in a maximum matching. (The reasoning here is that the cover is the $M$ edges of the matching plus one more edge for each unmatched vertex, and there are $n-2M$ unmatched vertices.)

$\endgroup$

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.