2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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
| cite | improve this answer | |
$\endgroup$

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.