<p>No, the variant is in P:</p>

<ol>
<li>for each element <span class="math-container">$x_i \in X$</span></li>
<li>find the set <span class="math-container">$A_{x_i}$</span> of triples "reachable" from <span class="math-container">$x_i$</span>:

<ul>
<li>start with all triples containing <span class="math-container">$x_i$</span> <span class="math-container">$A_{x_i} = \{ (x, y, z) \mid x = x_i \}$</span></li>
<li>iteratively add to <span class="math-container">$A_{x_i}$</span> all triples that share at least one element with all triples already in <span class="math-container">$A$</span></li>
</ul></li>
<li>check if <span class="math-container">$E \setminus A_{x_i}$</span> is a solution and also for each triple <span class="math-container">$(x,y,z) \in E$</span> check if <span class="math-container">$E \setminus (A_{x_i} \setminus \{ (x,y,z) \})$</span> is a solution (remove at most one triple from <span class="math-container">$A_{x_i}$</span>); if it's not a solution proceed with the next <span class="math-container">$x_i$</span> (step 1.)</li>
<li>if no solution is found, repeat the same algorithm 2–3 above "scanning" <span class="math-container">$y_i \in Y$</span> and checking <span class="math-container">$A_{y_i}$</span></li>
<li>if no solution is found, repeat the same algorithm 2–3 above "scanning" <span class="math-container">$z_i \in Z$</span> and checking <span class="math-container">$A_{z_i}$</span></li>
</ol>

<p>To prove that  it is correct note that each <span class="math-container">$A_{x_i}$</span> contains at most one element of the solution <span class="math-container">$M$</span> of the 3DM:</p>

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

CC BY-SA 4.0
2020-04-08T08:47:46.067Z
2020-04-08T09:43:47.923Z
2020-04-08T09:43:47.923Z
Marzio De Biasi
<p>In the normal version of the matching problem, we are given a set of vertices <span class="math-container">$X$</span>, <span class="math-container">$Y$</span>, and <span class="math-container">$Z$</span>, each of size <span class="math-container">$n$</span>, and a set of edges <span class="math-container">$E\subseteq X\times Y\times Z$</span>. We need to find a matching <span class="math-container">$M\subseteq E$</span> s.t. <span class="math-container">$|M| = n$</span> and it covers each element of <span class="math-container">$X$</span>, <span class="math-container">$Y$</span>, and <span class="math-container">$Z$</span> exactly once.</p>

<p>The variation is, can we find <span class="math-container">$M$</span> s.t. for any <span class="math-container">$(x_i,y_i,z_i), (x_j,y_j,z_j) \in E\smallsetminus M$</span>, <span class="math-container">$x_i = x_j$</span> or <span class="math-container">$y_i = y_j$</span> or <span class="math-container">$z_i = z_j$</span>?</p>

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

<graph-algorithms><np-hardness><matching><hypergraphs>
3-dimensional matching variant
utsi_boi
# 3-dimensional matching variant

(Asked by: username_0 on 2020-04-07)

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.

**Tags:** graph-algorithms, np-hardness, matching, hypergraphs

---

## 1 answers

### Answer by username_1 on 2020-04-08. Score: 2 | Accepted answer

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


---

