0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Welcome to CS.SE! In the future I encourage you to make your question self-contained by providing the definition of the problem. It might also help to tell us what you mean by "an example of some instance of the problem"; I bet there are trivial instances but I'm not sure whether they'll be helpful, so it would help if you told us how you plan to use it and your motivation. $\endgroup$ – D.W. Sep 13 '17 at 15:45
  • $\begingroup$ Thanks for the advice. I´ve already edited the question. $\endgroup$ – Mike Sep 13 '17 at 20:49
2
$\begingroup$

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.)

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Plexiglass doesn't float in water but let's ignore that. $\endgroup$ – David Richerby Sep 13 '17 at 15:24
  • $\begingroup$ It's probably also worth mentioning that, for each of the test questions, $C$ contains the set of items for which the answer is "yes". $\endgroup$ – David Richerby Sep 13 '17 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.