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[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 \mathcal{C} exists for X (the set containing the elements to be covered), containing a maximum of k sets

Showing the problem is in NP

Let \mathcal{C} = \{S_1, S_2, \ldots, S_n\} be the certificate. We assume that each S \in \mathcal{C} uniquely covers at least one x \in X, so:

(1)   \begin{align*}   |\mathcal{C}| &\leq |X|\\   \forall S \in \mathcal{C} : |S| &\leq |X| \end{align*}

This gives us that we can verify that n \leq k and that \mathcal{C} covers X in \mathcal{O}(|X|^2), 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)   \begin{equation*}   \textsc{Vertex-Cover} \leq_\text{P} \textsc{Set-Cover} \end{equation*}

Reduction

The vertex cover of an undirected graph G = (V, E) is a subset V' \subseteq V, such that each e \in E is adjacent to at least one v' \in V [1]. Its decision version is to determine whether a vertex cover of at most size k exists for G.

We can reduce any instance of decision-vertex-cover for G = (V, E) to an instance of decision-set-cover by letting X = E and letting the family of sets \mathcal{F} = {S_v | v \in V\ \land \text{deg}(v) > 0}, such that S_v contains all edges in E adjacent to v. We can perform this reduction in \mathcal{O}(|E| + |V|), 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)   \begin{align*}\mathcal{F} = \{S_{v_1} &= \{e_1, e_3\}, \\S_{v_3} &= \{e_2, e_5\},\\S_{v_4} &= \{e_3, e_6\},\\S_{v_6} &= \{e_4, e_7, e_8\}\}\end{align*}

We will now prove for any vertex cover V' for G and a set cover \mathcal{C} for sets X and \mathcal{F} constructed in accordance with the reduction above:

(4)   \begin{equation*}   \exists V'\subseteq V : |V'| \leq k \iff   \exists \mathcal{C} \subseteq \mathcal{F} : |\mathcal{C}| \leq k \end{equation*}

Since X = E, and we know V' is a vertex cover for G = (V, E), we can find \mathcal{C} for (X, \mathcal{F}) by selecting from \mathcal{F} all sets corresponding to v' \in V'.

Similarily, if \mathcal{C} exists, by the way we defined the reduction, we know it covers X = E. This means We can find V' by taking the vertices corresponding to S_v \in \mathcal{C}.

Due to the 1:1 correspondence of vertices in V' and sets in \mathcal{C}: |V'| = |\mathcal{C}|~\blacksquare

  1. [1]
    T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. MIT Press, 2009.

Leave a comment

Your email address will not be published. Required fields are marked *

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