Next: MINIMUM HITTING SET
Up: Covering, Hitting, and Splitting
Previous: MINIMUM EXACT COVER
  Index
- INSTANCE:
Collection C of subsets of a finite set S.
- SOLUTION:
A subcollection
such that for each pair of distinct elements
there is some set
that contains exactly one of
x1 and x2.
- MEASURE:
Cardinality of the subcollection, i.e., |C'|.
- Good News:
Approximable within
.
- Comment:
Transformation to MINIMUM SET COVER [267].
Observe that every solution has cardinality at least
.
- Garey and Johnson: SP6
Viggo Kann
1999-04-22