In Exercise 5 of Chapter 8, we claimed that the Hitting Set Problem was NP-complete. To recap the definitions, consider a set A = {al ..... an} and a collection B1. B2 ..... Bm of subsets of A. We say that a set H _ A is a hi.rig set for the collection BI. B~_ ..... Bm ff H contains at least one element from each B~--that is, ff H n B~ is not empty for each i. (So H "hits" all the sets B~.)

Now suppose we are given an instance of t~s problem, and wed like to determine whether there is a hitting set for the collection of size at most k. Furthermore suppose that each set B~ has at most c elements, for a constant c.

Give an algorithm that solves this problem with a running time that is exponentially smaller than brute force (i.e O(p(n,m)2ⁿ) where p(n,m) is polynomial in n,m)

Hint: Try to mimic algorithm for 3-CNFSAT