Problems for submission

1. Consider a set A = {a₁,..., an} and a collection B₁, B2,..., Bm of subsets

of A (i.e. B, CA for each i). We say that a set HCA is a hitting set

for the collection B₁, B2,..., Bm if H contains at least one element from

each B that is, if HB; is not empty for each i (so H "hits" all the

sets B₁). We now define the Hitting Set Problem as follows:

We are given a set A = {a₁,..., an}, a collection B₁, B2,..., Bm of subsets

of A, and a number k. We are asked: Is there a hitting set HCA for

B₁, B2,..., Bm so that the size of H is at most k?

(a) [4] Show that Vertex-Cover Sp Hitting-Set.

(b) [1] Show that Hitting-Set is in NP.