Consider a set A = {a1, . . . , an} and a collection B1, B2, . . . , Bm of subse
ID: 3573497 • Letter: C
Question
Consider a set A = {a1, . . . , an} and a collection B1, B2, . . . , 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, B2, . . . , Bm if H contains at least one element from each Bi – that is, if H Bi is not empty for each i (so H “hits” all the sets of Bi). We define the Hitting Set Problem as follows. We are given a set A = {a1, . . . , an}, a collection B1, B2, . . . , Bm of subsets of A, and an non-negative integer k. We are asked: is there a hitting set H A for B1, B2, . . . , Bm so that the size of H is at most k? Prove that the Hitting Set problem is NP-complete
Explanation / Answer
It can be shown in the following way:
This solutiion 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.