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

Answer 1

Answer:

Explanation:

This is actually quite straight forward to solve, first lets be mindful of the explanation so with this basis we can tackle future problems.

The solution may very well may be appeared in the accompanying manner:

This solution needs to display that the set H-one can without much of a stretch confirm in polynomial-time if H is of size k and meets every one of the sets B1.....Bm .

We lessen from Vertex Cover.Consider an example of the Vertex-Cover issue chart G=(V,E) and a positive whole number k.We map it to an occurrence of the hitting set issue as follows.The set An is of vertices V.

Also we know that For each edge e has a place with E we have a set Se Consisting of two end-purposes of e.It is anything but difficult to see that a lot of vertices S is a vertex front of G iff the relating components from a hitting set in the hitting set case.