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'\)).

Example of vertex cover (shaded nodes are 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} \]