# Set cover problem with sets of size 2

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.

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

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.)