I want to know whether the following kinds of special instances of the 3D Matching problem are ``yes" instances, i.e., admit a 3D matching.

We are given 3 sets $A,B,C$ containing $m$ elements each, and $n$ tuples $\{T_i\}_{i\in [n]}$ where $T_i \in A\times B\times C$. We further know:

(i) Each element of $A\cup B \cup C$ occurs exactly in two tuples. Simple counting shows $n = 2m$.

(ii) The elements of $A\cup B \cup C$ can be partitioned into $m$ singleton elements, and $m$ pairs $(x,y)$ where $\{x,y\} \subset T_i$ for some $i\in [n]$.

I want to know if such an instance admits a 3D matching. Is there a simple counter-example?


1 Answer 1


How about the following counter-example?

$m=2$, $n=4$.

$A=\{a_1,a_2\}$, $B=\{b_1,b_2\}$, $C=\{c_1,c_2\}$.

$T=\{(a_1,b_1,c_1), (a_1,b_2,c_2), (a_2,b_1,c_2), (a_2,b_2,c_1)\}$.

With the partition $A\cup B\cup C = \{a_1,b_1\}\cup\{a_2,b_2\}\cup\{c_1\}\cup\{c_2\}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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