4.13.4 Set Cover

Definition

Given a set U of size n, and collections of subsets of S₁,…,S_m ⊆ U. There exists a subset C ⊆{1,…,m}, such that ⋃ _iCS_i = U.

Polynomial Certifier

Question: Given a set U, collections of subsets of S₁,…,S_m ⊆ U, and a number k. Does there exists a subset C ⊆{1,…,m} of size k, such that ⋃ _iCS_i = U?

• Input: Given a set U, collections of subsets of S₁,…,S_m ⊆ U, and a number k
• Certificate: A subset C ⊆{1,…,m}
• Certifier: We can check if C is of the size k, and if each element in U is covered by at least one S_i,i C.
• Time Complexity: We can check if each element (n of them) in U that is covered by at least one S_i (n elements in m sets). Thus, O(n² ⋅ m).

Reduction from Vertex Cover from simple case to general case

We will construct the reduction as follow:
Let U = E(G), and for each vertex v₁,v₂,…,vn, we have a set S_i = {e E|v_i is incident on e}. That is, S_i is exactly the set of edges that v_i covers. Finally, we set k to be identical. This construction obviously can be done in polynomial in terms of |V | and |E|.

From the construction, Set Cover of the example above would be U = {1,2,3,4,5,6,7},S_a = {3,7},S_b = {2,4},S_c = {3,4,5,6},S_d = {5},S_e = {1},S_f = {1,2,5,6}, and U = S_c ∪ S_f.

VC is a Vertex Cover of size k in G ⇒ C is a set cover of at most k S_i′s,  v_i V , such that ⋃ _iCS_i = E.

C is a set cover of at most k S_i′s,  v_i V , such that ⋃ _iCS_i = E ⇒ VC is a Vertex Cover of size k in G.