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.