Question

3. (20 pts) Let ụ be a finite set, and let S = {Si, S , S,n} be a collection of subsets of U. Given an integer k, we want to know if there is a sub-collection of k sets S' C S whose union covers all the elements of U. That is, S k, and Us es SU. Prove that this problem is NP-complete. 992 m SES, si

Answer 1

Thm. Vertex Cover ≤ P Set Cover
Proof. Let G = (V , E ) and k be an instance of Vertex Cover.

Create an instance of Set Cover:
• U = E
• Create a S u for for each u ∈ V , where S u contains the edges
adjacent to u.
U can be covered by ≤ k sets iff G has a vertex cover of size ≤ k.
Why?

If k sets S u 1 , . . . , S u k cover U then every edge is adjacent to
at least one of the vertices u 1 , . . . , u k , yielding a vertex cover of
size k.
If u 1 , . . . , u k is a vertex cover, then sets S u 1 , . . . , S u k cover U.

We still have to show that Set Cover is in NP!
The certificate is a list of k sets from the given collection.
We can check in polytime whether they cover all of U.
Since we have a certificate that can be checked in polynomial time,
Set Cover is in NP.