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

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

Problem statement

Showing the problem is in NP

Showing the problem is NP-hard

Reduction

Leave a comment

Cancel reply