#Notes: Proving HITTING SET problem as NP Complete

Problem : HITTING SET

Statement :

In the HITTING SET problem, we are given a family of sets {S₁, S₂, . . . , S_n} and a budget b, and we wish to find a set H of size ≤ b which intersects every S_i , if such an H exists. In other words, we want H ∩ S_i ≠ ∅ for all i. Show that HITTING SET is NP-complete.

Reference - DPV 8.19

Solution:

We will try to solve the problem by proving HITTING SET problem as NP Complete in following steps:

1. HITTING SET problem is NP Problem.

Argument → For a given solution H of the problem, we can check if size |H|≤ b and that H ∩ S_i ≠ ∅. Since we can find out the intersection between sets in O(n²) time by checking each element of one set in another, to compare m sets it will take total O(mn²) time, which is in polynomial time.

1. HITTING SET problem is as hard as the VERTEX COVER problem. We will apply reduction VERTEX COVER → HITTING SET.

   1. Input to VERTEX COVER can be converted into input to HITTING SET in polynomial time.

      Argument → Formally VERTEX COVER problem is given a graph G(V,E), we need to find a subset of vertices V’ such that for |V'| ≤ k and all edges e =u,v ∈ E , u ∈ V’ ∨ v ∈ V’ .

      For every edge e = (u,v) we can construct a Set S_e = {u,v} , we will have total number of set |S| = |E| = m and we set budget b = k.

      The construction of the set will take O(|E|) time, which is in polynomial time.

   2. Solution to the HITTING SET problem can be converted to solution for VERTEX COVER in polynomial time.

      Argument → The solution of HITTING SET will give a set H, such that |H| ≤ b. The set H can be taken as a set of vertices of graph G(V,E) as V’, which has size ≤ k ( as b = k). Thus the solution of HITTING SET can be converted to solution to VERTEX COVER directly ( in O(1) which is polynomial time).

   3. Solution to HITTING SET exists iff solution to VERTEX COVER problem.

      Argument → We can prove that if there is a solution to VERTEX COVER solution then there is a solution to HITTING SET problem and vice versa.

      Let V’ be the vertex cover for G(V,E) of size |V|≤ k. Thus for every edge e = (u,v), either u ∈ V’ or v ∈ V’. For edge (u,v) we have constructed the set S_e = {u,v} , thus S_e ∩ V’ ≠ ∅. Thus, we have found a set V’ such that it intersects every set S_e. Hence if we take V’ = H, we have found solution to the HITTING SET problem.

      Lets H ( |H| ≤ b) be a solution to a family of sets {S₁, S₂ .. S_m } for HITTING SET problem. That means that for every set S_e , S_e ∩ H ≠ ∅, means there H has at least one element of the set S_e. If we consider S_e as a set containing edge vertices u and v, such at e = (u,v) e ∈ E, u,v ∈ V for a graph G(V,E), the set H has vertices h ∈ V such that at least one member of S_e is present in H. Thus H is a solution for the VERTEX COVER problem for graph G(V,E).

      Thus, Solution to VERTEX COVER exists iff solution to HITTING SET problem.

Thus HITTING SET is a NP Complete problem.