# Struggling with NP-Complete Problem

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.

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

• 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. Apr 26, 2020 at 21:14
• Is it clearer now? Apr 26, 2020 at 21:20
• 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$? Apr 26, 2020 at 21:39
• It should be $\le$ ! I fixed it. Apr 26, 2020 at 21:41
• Awesome, you rock. Thanks a lot, @Steven! Apr 26, 2020 at 21:44