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 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:

$\begin{aligned} |\mathcal{C}| &\leq |X|\\ \forall S \in \mathcal{C} : |S| &\leq |X| \end{aligned}$

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:

$\text{Vertex-Cover} \leq_\text{P} \text{Set-Cover}$

Reduction

A 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$ . 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 clearly perform this reduction in $\mathcal{O}(|E| + |V|)$ , which is in polynomial time.

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:

$\exists V'\subseteq V : |V'| \leq k \iff \exists \mathcal{C} \subseteq \mathcal{F} : |\mathcal{C}| \leq k$

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$

Example

An example is probably useful here. See the image below for an example of a vertex cover of size 4 (with shaded nodes being in $V'$ ).

The result of performing the reduction for this example is:

$\begin{aligned} \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{aligned}$