- 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 and .
- MEASURE:
Cardinality of the subcollection, i.e., .

*Good News:*Approximable within .*Comment:*Transformation to MINIMUM SET COVER [282]. Observe that every solution has cardinality at least .*Garey and Johnson:*SP6