MINIMUM TEST COLLECTION

• INSTANCE: Collection C of subsets of a finite set S.
• SOLUTION: A subcollection $C'\subseteq C$ such that for each pair of distinct elements $x_1,x_2\in S$ there is some set $c\in C'$ that contains exactly one of $x_1$ and $x_2$.
• MEASURE: Cardinality of the subcollection, i.e., $\vert C'\vert$.

  
  

• Good News: Approximable within $1+2\ln\vert S\vert$.
• Comment: Transformation to MINIMUM SET COVER [282]. Observe that every solution has cardinality at least $\lceil \log\vert S\vert \rceil$.
• Garey and Johnson: SP6