# 3-dimensional matching variant

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.

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