Next: MINIMUM HITTING SET Up: Covering, Hitting, and Splitting Previous: MINIMUM EXACT COVER Index

### MINIMUM TEST COLLECTION

- 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