# Proving the set-covering problem is NP-complete (using reduction from the vertex-cover problem)

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.

## Problem statement

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:

(1) 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:

(2) ### Reduction

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. Example of vertex cover (shaded nodes are in V’)

The example image above shows a vertex cover of size. Making the reduction for this example gives:

(3) We will now prove for any vertex cover for and a set cover for sets and constructed in accordance with the reduction above:

(4) 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 : 1. 
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. MIT Press, 2009.

## Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.