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.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ There is no explanation there why is it so, and it seems that the author doesn't sure in his answer. $\endgroup$– RbixJul 5, 2017 at 12:51
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
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.)
answered Jul 5, 2017 at 15:02