Example of Minimum Test Collection Problem

Question

I'm studying the Minimum Test Collection problem and I can't find an example of some instance of the problem, given values to the sets. The Garey and Johnson book only contains the proof of its NP-Completeness.

I hope someone can give me an example in order to understand in a better way the problem.

The problem is defined as follows:

Instance: A finite set A of "possible diagnoses," a collection C of subsets of A, representing binary "tests," and a positive integer J≤|C|.

Question: Is there a subcollection C′⊆ C with |C′|≤ J such that, for every pair $a_{i},a_{j}$ of possible diagnoses from A, there is some test c∈C′ for which |{$a_{i},a_{j}$}|∩ c|=1 (that is, a test c that "distinguishes" between $a_{i}$ and $a_{j}$)?

Thanks.

Answer 1

The formal definition of the problem from Garey and Johnson is

Minimum Test Collection

Instance: A finite set $A$ of "possible diagnoses," a collection $C$ of subsets of $A$, representing binary "tests," and a positive integer $J\leq |C|$.

Question: Is there a subcollection $C'\subseteq C$ with $|C'|\leq J$ such that, for every pair $a_i,a_j$ of possible diagnoses from $A$, there is some test $c\in C'$ for which $|\{a_i,a_j\}|\cap c|=1$ (that is, a test $c$ that "distinguishes" between $a_i$ and $a_j$)?

Think of $A$ as a set of diseases, and each element of $C$ is a set of all the diseases in $A$ that have some particular symptom. You can use these sets to figure out what disease a person has. For example (not necessarily medically accurate), suppose our diseases are $$A = \{\mathrm{flu}, \mathrm{measles}, \mathrm{ebola}\}$$ and our tests are $$C = \{\mathrm{cough}, \mathrm{rash}, \mathrm{bleeding}\}\,,$$ where \begin{align*} \mathrm{cough} &= \{\mathrm{flu}, \mathrm{ebola}\}\\ \mathrm{rash} &= \{\mathrm{measles}, \mathrm{ebola}\}\\ \mathrm{bleeding} &= \{\mathrm{ebola}\}\,. \end{align*}

A doctor might try to diagnose a patient by checking whether they have a cough and/or a rash and whether they're bleeding. Minimum Test Collection asks if we can do any better than that, since tests might be expensive to carry out.

In this case, we can. It's enough to check whether the patient is coughing and whether they're bleeding. If they're bleeding, we know they have ebola. If they're not bleeding, but they are coughing, they have the flu; if they're neither bleeding nor coughing, they must have the measles. (Note we're assuming as part of our test procedure that these are the only three diseases in the world, and that people only go to the doctor if they have at least one symptom.)

Answer 2

In the Minimum Test Collection Problem you have some universe $S$ of items that you want to distinguish and a collection $C$ of tests that for a given item are either positive or negative. You want to select a minimal subset $C'\subseteq C$ of these tests that allow you to distinguish every pair of items.

For example you can have the items {Plexiglass, Glass, Wood} and the tests "Does it float?" (Wood, Plexiglass), "Does it burn?" (Wood, Plexiglass), "Is it transparent?" (Plexiglass, Glass). You can select the tests "Does it float?" and "Is it transparent?" to distinguish the items:

• Plexiglass, Wood: Both float, but only Plexiglass is transparent
• Plexiglass, Glass: Both are transparent, but only Plexiglass floats
• Glass, Wood: Only Glass is transparent, only Wood floats.

For every single test there is a pair where the test is true for both, so you can't select only one test.