3-dimensional matching variant

Question

In the normal version of the matching problem, we are given a set of vertices $X$, $Y$, and $Z$, each of size $n$, and a set of edges $E\subseteq X\times Y\times Z$. We need to find a matching $M\subseteq E$ s.t. $|M| = n$ and it covers each element of $X$, $Y$, and $Z$ exactly once.

The variation is, can we find $M$ s.t. for any $(x_i,y_i,z_i), (x_j,y_j,z_j) \in E\smallsetminus M$, $x_i = x_j$ or $y_i = y_j$ or $z_i = z_j$?

This is the decision version of the 3d-matching variant. I wanted to know if this would also be NP-complete.

Answer 1

No, the variant is in P:

1. for each element $x_i \in X$
2. find the set $A_{x_i}$ of triples "reachable" from $x_i$:
   • start with all triples containing $x_i$ $A_{x_i} = \{ (x, y, z) \mid x = x_i \}$
   • iteratively add to $A_{x_i}$ all triples that share at least one element with all triples already in $A$
3. check if $E \setminus A_{x_i}$ is a solution and also for each triple $(x,y,z) \in E$ check if $E \setminus (A_{x_i} \setminus \{ (x,y,z) \})$ is a solution (remove at most one triple from $A_{x_i}$); if it's not a solution proceed with the next $x_i$ (step 1.)
4. if no solution is found, repeat the same algorithm 2–3 above "scanning" $y_i \in Y$ and checking $A_{y_i}$
5. if no solution is found, repeat the same algorithm 2–3 above "scanning" $z_i \in Z$ and checking $A_{z_i}$

To prove that it is correct note that each $A_{x_i}$ contains at most one element of the solution $M$ of the 3DM:

• by your variation constrait $E \setminus M$ is contained in at least one of the $A_{x_i},A_{y_i},A_{z_i}$, suppose $A_{x_i}$: $E \setminus M \subseteq A_{x_i}$;
• furthermore $M \cap A_{x_i}$ must contain at most one triple from $A_{x_i}$, otherwise the 3DM constraint “covers each element of $X$, $Y$ and $Z$ exactly once” would be violated