$5.$ ConsiderasetA$=\{$a$1,...,$an$\}$and a collection B$1,$B$2,...,$Bm ofsubsetsof A $($i$.$e$.,$ Bi $$ A for each i$).$

We say that a set H $$ A is a hitting set for the collection B$1,$B$2,...,$Bm if H contains at least one element from each Bi$$that is$,$ if H $\backslash$cap Bi is not empty for each i $($so H $$hits$$ all the sets Bi$).$

We now define the Hitting Set Problem as follows. We are given a set A$=\{$a$1,...,$an$\},$ a collection B$1,$B$2,...,$Bm of subsets of A$,$ and a number

k$.$ We are asked: Is there a hitting set H $$ A for B$1,$B$2,...,$Bm so that the size of H is at most k$?$

Prove that Hitting Set is NP$-$complete. Hints$/$direction: There are two runtimes that need to be discussed when proving a problem NP$-$Complete.

First, we want to argue the verification algorithm is able to check a certificate for the yes$-$instance. Start by saying what a certificate would be for a yes$-$instance, as that will be the input to your verifier since that is the thing you are verifying. $($Again you can refer to sample solutions from last HW for help with making this more concrete. Also see the HW hints I posted last week that referred to places in the textbook that gave examples of this.$)$

Second, we want to prove that some already$-$known$-$to$-$be NP$-$hard problem is polytime reducible to whatever textbook problem you are working on$.$ Verification algorithm $+$ run time $(6$points$)$

Reduction algorithm $(5$ points$)$

Proof of correctness of reduction $(4$ points$)$

Runtime analysis of reduction $(2$ points$)$ Vertex Cover would work well for showing Hitting Set is NP$-$hard

Remember you are starting with VC and building a Hitting Set input from it

Some people had the right idea for the proofs but left out basic info such as explaining each node in the vertex cover graph $($which is the input you start with$)$ corresponds to an element in the set A in the hitting set instance $($which is what you are building$).$ Steps like this are crucial in proving how you know a solution for the vertex cover problem corresponds to a solution in the hitting set instance.