Struggling with NP-Complete Problem

Question

I have a practice exam question that I am looking for help with. It is regarding proving NP-Completeness using Reduction. The problem is as follows:

The Set Cover problem is the following:

Instance: A set $U = \{1,2,...,n\}$ of $n$ elements, a collection of subsets $S_1,S_2,...,S_m$ of U, and an integer $K$.

Question: Are there $K$ sets among the $S_i$’s whose union is equal to $U$? In other words, are there $K$ sets which together cover all the elements of $U$?

Prove that Set Cover is NP-complete

Any guidance here would be greatly appreciated. My thought is that I should try reducing from the Vertex Cover problem, but I am not entirely sure how to reduce from there.

Answer 1

An instance of (the decision version of) vertex cover is a pair $\langle G, k \rangle$ where $G = (V,E)$ is a graph and $k$ is an integer. The problem is that of deciding whether $\exists S \subseteq V$ such that $|S| \le k$ and $\forall (u,v) \in E, \; \{u,v\} \cap S \neq \emptyset$.

Let $v_1, \dots, v_n$, be the vertices of $V$, in an arbitrary order.

You can see that vertex cover is a special case of set-cover. Indeed, it suffices to define $U=E$, $S_i = \{u \in V : (v_i, u) \in E \}$ for $i=1,\dots,n$, and $K = k$.

If there is a set-cover $C$ of size at most $K$, then for each element $e = (v_i, v_j) \in U = E$ at least one of $V_i$ and $V_j$ is in $C$ (since these are the only two sets that contain $e$). This means that $S = \{v_h : V_h \in C \}$ is a vertex-cover for $G$ of size $|S| = |C| \le K = k$.

If there is a vertex cover $S$ of size at most $k$ for $G$, then for each edge $e = (v_i, v_j) \in E = U$, $\exists v_k \in \{v_i, v_j\} \cap S$. This means that $V_k \ni e$ is in the set $C = \{ V_h : v_h \in S \}$ and hence $C$ is a set-cover of size $|C|=|S| \le k=K$.