It is easy to show that Hitting Set is in NP. A solution just needs to
exhibit the set H – one can easily verify in polynomial time whether H is of size k and
intersects each of the sets B1, . . . , Bm.
We reduce from vertex cover. Consider an instance of the vertex cover problem –
graph G = (V, E) and a positive integer k. We map it to an instance of the ...