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}$)?

And we know that MTC is $NP$-complete, it has been proved by reducing it to 3 Dimensional Matching problem in the Garey & Johnson's book.


  • $\begingroup$ I imagine that Garey and Johnson reduced 3DM to (not from) MTC, since only this direction establishes the NP-completeness of MTC. $\endgroup$ – j_random_hacker Oct 28 '17 at 13:19

Yes, there are approximation algorithms for this problem.

  1. If $k$ is the upper bound of the test case, the authors of http://repository.cmu.edu/cgi/viewcontent.cgi?article=1397&context=tepper constructed a $O(\log{k})$-approximation algorithm
  2. Another approximation algorithm of the same complexity is derived here: https://link.springer.com/chapter/10.1007/3-540-44676-1_13

Hope that helps!

| cite | improve this answer | |

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.