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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.)