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[1]. 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[1], 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 [1]. 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:

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