Consider a set A = {a1, . . . , an} and a collection B1, B2, .
Fantastic news! We've Found the answer you've been seeking!
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
Related Book For
Discrete and Combinatorial Mathematics An Applied Introduction
ISBN: 978-0201726343
5th edition
Authors: Ralph P. Grimaldi
Posted Date: