0

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

Thanks.

Rbix
  • 13

1 Answers1

0

The SET COVER problem with all sets having size 2 is equivalent to the EDGE COVER problem (each element in $U$ becomes a vertex in the graph, and each subset becomes an edge).

EDGE COVER can be solved in polynomial time by constructing a maximum matching (for example, using Edmond's algorithm) and then extending the matching to cover all the vertices.

Gareth Rees
  • 661