In this post, we will prove that the decision version of the set-covering problem is NP-complete, using a reduction from the vertex covering problem (which is NP-complete). This is Exercise 35.3-2 in CLRS3. We will follow the template given in an earlier post.
We will use the definition for a set cover given on page 1118 in CLRS3, also given on Wikipedia. Since we’re concerned with the decision version, we seek to answer whether a set cover exists for (the set containing the elements to be covered), containing a maximum of sets
Showing the problem is in NP
Let be the certificate. We assume that each uniquely covers at least one , so:
This gives us that we can verify that and that covers in , which proves the problem is in NP.
Showing the problem is NP-hard
We will show that the decision version of the set-covering problem is NP-hard by showing:
The vertex cover of an undirected graph is a subset , such that each is adjacent to at least one . Its decision version is to determine whether a vertex cover of at most size exists for .
We can reduce any instance of decision-vertex-cover for to an instance of decision-set-cover by letting and letting the family of sets , such that contains all edges in adjacent to . We can perform this reduction in , which is in polynomial time.
The example image above shows a vertex cover of size. Making the reduction for this example gives:
We will now prove for any vertex cover for and a set cover for sets and constructed in accordance with the reduction above:
Since , and we know is a vertex cover for , we can find for by selecting from all sets corresponding to .
Similarily, if exists, by the way we defined the reduction, we know it covers . This means We can find by taking the vertices corresponding to .
Due to the 1:1 correspondence of vertices in and sets in :
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. MIT Press, 2009.