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.

Answer 2

Following are the illustration to the given question:

• The solution must demonstrate that only if H is of size k and overlaps each one of the sets B1.....Bm, can one simply verify it in time complexity.
• You start with Vertex Cover and decrease from there.
• Considering the Vertex-Cover issue graph G = (V, E) with a positive integer k as an example.
• As shown below, we map this to a hitting set issue case V are the vertices of set A.
• It has the set Se that includes 2 end-points of e for each edge of e belonging to E.
• A vertex set "S" covers vertex "G" if the matching members from a hitting set were present in the striking setting instance.

Learn more set:

brainly.com/question/2264459

brainly.com/question/8053622