- INSTANCE:
Collection
*C*of subsets of a finite set*S*. - SOLUTION:
A hitting set for
*C*, i.e., a subset such that*S'*contains at least one element from each subset in*C*. - MEASURE:
Cardinality of the hitting set, i.e., .

*Good News:*See MINIMUM SET COVER.*Bad News:*See MINIMUM SET COVER.*Comment:*Equivalent to MINIMUM SET COVER [46]. Therefore approximation algorithms and nonapproximability results for MINIMUM SET COVER will carry over to MINIMUM HITTING SET. The constrained variation in which the input is extended with a subset*T*of*S*, and the problem is to find the hitting set that contains the largest number of elements from*T*, is not approximable within for some [476]. Several special cases in which, given compact subsets of , the goal is to find a set of straight lines of minimum cardinality so that each of the given subsets is hit by at least one line, are approximable [236].*Garey and Johnson:*SP8