4.13.2 Hitting Set

Definition

Given a set A = {a₁,…,a_n}, a collection B₁,B₂,…,B_m of subsets of A, and a number k. There exists a Hitting Set H ⊆ A of size k, such that H ∪ B_i≠∅,1 ≤ i ≤ m.

Polynomial Certifier

• Input: Given a set A = {a₁,…,a_n}, a collection B₁,B₂,…,B_m of subsets of A, and a number k.
• Certificate: A Hitting Set H ⊆ A.
• Certifier: we can check in polynomial time whether H has size at most k, and whether some member of each set B_i belongs to H.
• Time Complexity: We can brute-forced check if B_i intersects with H O(n²) for m times, that is O(n² ⋅ m).

Reduction from Vertex Cover from simple case to general case

Given a graph G = (V,E) and a number k, we first define the set A in Hitting Set instance to be the V of nodes in the Vertex Cover instance. For each edge e_i = (u_i,v_i) E, we define a set B_i = {u_i,v_i} in the Hitting Set instance

From the construction, B₁ = {x₁,x₃},B₂ = {x₂,x₃},B₃ = {x₃,x₄},B₄ = {x₃,x₅},B₅ = {x₄,x₅},B₆ = {x₄,x₆},B₇ = {x₅,x₆},B₈ = {x₆,x₇}. Hitting Set is the Vertex Cover {x₃,x₅,x₆}, and the requirement of being a hitting set holds.

The original graph had a vertex cover of size at most k ⇒ there is a hitting set of size at most k for this instance

There is a hitting set of size at most k for this instance ⇒ The original graph had a vertex cover of size at most k