Question

5. The Hitting Set Problem (HS) is the following decision problem. Input. A finite set S, a collection (s1, s2,... , sn) of subsets of S, and a positive integer K. Question. Does there exist a subset t of S such that (a) t has exactly K members and (b) for i 1,..., n, sint6For example, suppose S # {1, 2, 3, 4, 5, 6, 7. the collection of subsets is (2.45), (34).(1,35) and K - 2. Then the answer is yes, since t (1, 4) meets the requirement: t has K members and each of the given subsets contains a member of t. Answer the following questions. (a) Show that the Hitting Set Problem is in NP (b) Let VC be the Vertex Cover Problem. Show that VC sp HS (c) VC is known to be NP-complete. Are your results from parts (a) and (b) enough to conclude that HS is NP-complete? (d) Show that HS sp VC. You may use the fact that VC is NP-complete.

Answer 1

a. Htting set problem is in NP because given any set t as the solution, we can verify whether t has k elements and every subset si has some element which is also the element of t, in polynomial time. So this problem is in NP.

b. We can reduce VC problem instance where in graph G, we have to determine whether G has vertex cover of size k into the HS problem instance in polynomial time as follows :-

Corresponding to every vertex v in the graph, create a subset s_v which contains vertex v and all the vertices which are neighbors of v.

Claim :- If graph G has VC of size k, then the reduced problem will have hitting set t of size k which contains some element from all the subsets .

proof :- If G has VC of size k, then these vertices will cover entire vertices of the graph G, then by taking these vertices as member of solution t, we will get set t of size k, and since these vertices have edge towards all remaining vertices in the graph, corresponding subset will be covered by these k elements.

Similarly if graph G does not have VC of size k, then HS will not be able to get k elements which covers some element from every subset. Hence this reduction will give equivalent result.

And this reduction is polynomial time reduction. So $VC \leq_p HS$ .

C. Yes since VC is NP-hard because of being NP-complete and $VC \leq_p HS$ so HS is also NP hard and since HS is also in NP, so HS is NP ccomplete.

d. Given the instance of HS, we can reduce this to problem instance of VC as :-

1. Represent every element of finite set S as the vertices of graph G and

2. Draw an edge between 2 vertices if they are part of same subset among every collection of subsets.

If graph G contain vertex cover of size k, then HS will have hitting set of size k. Using similar reduction, we can show that VC has yes instance for the reduced problem if and only if HS have yes instance for original problem. So $HS \leq_p VC$

Please comment for any clarification