MINIMUM HITTING SET

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

  
  

• 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 $\vert S\vert^{\varepsilon }$ for some $\varepsilon >0$ [476]. Several special cases in which, given compact subsets of $R^d$, 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