Question

Consider a set A = {a1, . . . , an} and a collection B1, . . . , Bm of subsets of A (i.e. Bi ⊆ A for each i.) We say that a set H ⊆ A is a hitting set for the collection B1, . . . , Bm if H contains at least one element from each Bi - that is, if H T Bi is not empty for each i (so H hits all the sets Bi .) We now define the hitting set problem as follows. We are given a set A = {a1, . . . , an}, a collection B1, . . . , Bm of subsets of A, and a number k. We are asked: Is there a hitting set H ⊆ A for B1, . . . , Bm so that the size of H is at most k? Prove that hitting set is NP-complete.

Answer 1

Check the explanation

Explanation:

It can be shown in the following way:

This solution needs to exhibit that the set H-one can easily verify in polynomial-time if H is of size k and intersects each of the sets B1.....Bm .

We reduce from Vertex Cover.Consider an instance of the Vertex-Cover problem graph G=(V,E) and a positive integer k.We map it to an instance of the hitting set problem as follows.The set A is of vertices V.For every edge e belongs to E we have a set Se Consisting of two end-points of e.It is easy to see that a set of vertices S is a vertex cover of G iff the corresponding elements from a hitting set in the hitting set instance.