A hitting set for a collection 
of subsets of a finite set 
is a subset 
such that
 |
for every 
.
The hitting set problem asks, for a positive integer 
, whether such an 
exists with 
.
Hitting set is the dual of the set cover problem: interchanging the elements of 
with the members of 
converts instances of either problem into instances of the
other. It is NP-complete. A vertex
cover is the special case obtained by taking 
to be the vertex set of a graph and 
to consist of the two-element subsets
corresponding to its graph edges.
