0
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$

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$.

$\endgroup$
5
  • $\begingroup$ I'm not sure I completely follow the notation here. Any way you could describe a bit more about what you mean? Also, thank you for the very quick reply and reformatting of the question text. $\endgroup$ Apr 26, 2020 at 21:14
  • $\begingroup$ Is it clearer now? $\endgroup$
    – Steven
    Apr 26, 2020 at 21:20
  • $\begingroup$ Definitely clearer. Thank you. One last piece of clarification. Should the final line say that $|C| = |S| \leq k = K$, or is it correct that it should just be "=", not $\leq$? $\endgroup$ Apr 26, 2020 at 21:39
  • $\begingroup$ It should be $\le$ ! I fixed it. $\endgroup$
    – Steven
    Apr 26, 2020 at 21:41
  • $\begingroup$ Awesome, you rock. Thanks a lot, @Steven! $\endgroup$ Apr 26, 2020 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.