217k views
2 votes
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.

1 Answer

6 votes

Answer:

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.

User Selva
by
8.6k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories