<p><strong>EDIT (Aug 1):</strong></p>

<p>I posted a small report with a more detailed proof <a href="http://www.nearly42.org/npc-pills/npc-pill-003/" rel="nofollow noreferrer">on my blog</a>; the reduction idea is the same, but the "gadget" used are better explained (you can also directly <a href="http://www.nearly42.org/vdisk/pills/3dmvariant.pdf" rel="nofollow noreferrer">download the pdf from here</a>)</p>

<hr>

<p>The problem seems NP-complete and this is a possible reduction from SET COVER.</p>

<p>Suppose you have an universe $A$ of $n$ elements: $A = \{a_1,...,a_n\}$, a collection of $m$ subsets $\mathcal{S} = \{S_1,S_2,...,S_m\}$ (with $S_i \subseteq A$) and an integer $k$. The SET COVER problem asks for a sub-collection $\mathcal{C} \subseteq \mathcal{S}$ of size at most $k$ such that $\bigcup_{S_i \in \mathcal{C}} S_i = A$ (with $|\mathcal{C}| \leq k$).</p>

<p>The reduction to your problem (I call it 3DM-relaxed, 3DMR) can be done in the following way.</p>

<p>The subsets $S_i$ are simulated using one or more elements of the set $X$, the elements of the universe $A$ are simulated using elements of the sets $Y$ and $Z$ ($a_{2j}$ is simulated with an element $y_{a_{2j-1}}$ of $Y$, $a_{2j-1}$ is simulated with an element $z_{a_{2j}}$  of $Z$).</p>

<p>We start with $X = \{ e_1,e_2,...,e_{k} \}$ that will force the $|\mathcal{C}|=k$ constraint.</p>

<p>Then, for every subset $S_i$ we create the triple: $(x^1_{S_i}, y_{S_i}, dum)$, where $dum$ is a new element of $Z$; and add the $k$ triples:<br><br>
 $(e_1,y_{S_i}, dum),(e_2,y_{S_i}, dum),...,(e_{k},y_{S_i}, dum)$</p>

<p>Note that <em>all</em> $dum$ elements are distinct!</p>

<p>In this way <strong>at most</strong> $k$ of the $x^1_{S_i}$ will be "free" to cover the elements representing the $a_j$: indeed the $(e,\cdot,\cdot)$ triples can include at most $k$ of the $y_{S_i}$, the remaining $m-k$ must be included by the corresponding $(x^1_{S_i},\cdot,\cdot)$ triple.</p>

<p>To link the $x^1_{S_i}$ to the elements $y_{a_{2j}}, z_{a_{2j-1}}$ that correspond to the elements of the universe in $S_i$, we add three <em>bridge</em> triples:<br>
$(x^1_{S_i},y_{B_i},z_{B_i})$,<br>
$(x^2_{S_i},y_{B_i},dum)$,<br>
$(x^3_{S_i},dum,z_{B_i})$</p>

<p>At this point the elements of $A$ can be linked to $x^2_{S_i}$ and $x^3_{S_i}$ (or we can further extend the capacity of $S_i$ adding more bridge triples).</p>

<p>For example adding the triples:</p>

<p>$(x^2_{S_i},y_{a_2},z_{a_1}), (x^3_{S_i},y_{a_4},z_{a_3})$ we simulate the set: $S_i = \{ a_1, a_2, a_3, a_4\}$.</p>

<p>The fundamental point is that if $x^1_{S_i}$ is "used" to cover the element $y_{S_i}$ (blue edges in the figure) then:</p>

<ul>
<li>$x^2_{S_i}$ <em>must</em> be used to include element $y_{B_i}$ and cannot be used to include elements $y_{a_2}, z_{a_1}$ (red edges in the figure);</li>
<li>$x^3_{S_i}$ <em>must</em> be used to include element $z_{B_i}$ and cannot be used to include elements $y_{a_4}, z_{a_3}$ (red edges in the figure).</li>
</ul>

<p>Some of the $S_i$ included in the cover can have a  non-empty intersection; so we must be sure that two distinct $x^p_{S_i}, x^q_{S_j}$ that are linked to the same element $a_i$ (i.e. we have the triples $(x^p_{S_i}, a_i, \cdot), (x^q_{S_j}, a_i, \cdot)$) can be included in the matching. For this purpouse for every $x^p, p &gt; 1$ we add a triple with two dum elements: $(x^p, dum, dum)$ (green edges in the figure below).</p>

<p>Finally we can add as many distinct triples $(x, y, dum_i), (x, dum_j, z)$ as needed to be able to <em>garbage collect</em> all the dum elements $dum_i \in Z$ and the dum elements $dum_j \in Y$ (otherwise the would not be included in the matching) if they are left alone.</p>

<p>Also note that if there are too many $S_i$, the elements $e_i$ can be included in the matching using their $z_{dum}$ element in $Z$ (only the pair $(e_i, z_{dum})$ is picked).</p>

<p>The resulting 3DMR instance has a solution if and only if there is an set cover $\mathcal{C}$ of $A$ of size at most $k$.</p>

<p><img src="https://i.sstatic.net/aUH2F.png" alt="enter image description here"></p>

<p>In the figure a triple $(x,y,z)$ is represented with two edges $(x,y),(x,z)$ of the same color. As an example, if $x^1_{S_1}$ corresponding to $S_1 = \{a_1,a_2,a_3,a_4\}$, must be used to include $y_{S_1}$ (blue edges), then it cannot be used to include the elements $z_{a_1},y_{a_2},z_{a_3},y_{a_4}$ (red edges).</p>

CC BY-SA 3.0
2014-05-12T01:30:51.367Z
I'm pretty sure that your transformation would result in solutions that aren't valid in the original graph (as long as we are thinking of the same problem; maybe my description still isn't right?). For instance if the original graph contains only the edges $(x,y_1,z_1)$ and $(x,y_2,z_2)$ then the new graph will allow a solution containing both $(x,y_1)$ and $(x'',z_2)$ which would correspond to a nonexistent edge $(x,y_1,z_2)$.
Rex Fernando
CC BY-SA 3.0
2014-05-12T06:52:47.400Z
@RexFernando: mmm ... perhaps you're right ... but the 2DM solution must also contain $y_2$ and $z_1$ which seems not possible (i.e. $M' = \{(x,y_1),(x'',z_2)\}$ is not a valid solution for the 2DM) ... can you show a full example of non-working instance. Meanwhile I'll think more about the correctness of my proof.
Marzio De Biasi
CC BY-SA 3.0
2014-05-14T15:01:03.213Z
You were right; perhaps I found a NP-hardness reduction. But it's a little bit complex, so perhaps it needs fixes (or simply it is wrong :-). Let me know.
Marzio De Biasi
CC BY-SA 3.0
2014-05-16T14:36:57.397Z
@RexFernando: did you check the reduction? If it is correct and the problem is not known, we could write a small report.
Marzio De Biasi
CC BY-SA 3.0
2014-05-17T05:16:44.463Z
Just saw your post, I will check it and get back to you.
Rex Fernando
CC BY-SA 3.0
2014-05-27T09:14:45.933Z
@RexFernando: did you check it (or do you need clarifications)?
Marzio De Biasi
CC BY-SA 3.0
2014-05-29T00:36:58.650Z
Can I get back to you next week? I took a quick look at it but it seems pretty involved, and i am on vacation now.
Rex Fernando
CC BY-SA 3.0
2014-05-12T00:10:46.213Z
2014-07-31T23:34:09.193Z
2014-07-31T23:34:09.193Z
Marzio De Biasi
<p>I am thinking about a variant of 3-dimensional matching. In normal 3d matching, we have three sets of vertices $X$, $Y$ and $Z$, and a set of edges $E \subseteq X \times Y \times Z$. We want to choose a matching $M \subseteq E$ of maximum size. </p>

<p>I would like to instead choose $M$ from the set $E \cup \{(x,w) \bigm| \exists z: (x,w,z) \in E \vee \exists y: (x,y,w) \in E\}$. So for each triple in $E$, assume that choosing a pair with the first and second elements or a pair with the first and third elements to be part of $M$ would also be acceptable. (Note that a pair with the second and third elements is not allowed.) The question is if there a matching $M$ that covers every element in $X \cup Y \cup Z$ exactly once.</p>

<p>I was wondering whether this problem is still hard. The Garey &amp; Johnson proof of NP-hardness of 3d matching seems to break down; if $M$ is chosen as specified above, the gadget for the variable doesn't work anymore. </p>

CC BY-SA 3.0
2014-05-11T21:58:33.223Z
Your problem is a generalization of 3DM (so it is still NPC): given an instance of 3DM, just pick the same M (i.e. $M \cap (W \times X) = M \cap (W \times Y) = \emptyset$) and you get an instance of your variant that has a solution iif the original 3DM instance has a solution.
Marzio De Biasi
CC BY-SA 3.0
2014-05-11T22:26:42.187Z
The problem is that there are instances of 3DM that don't have a solution but where the corresponding instance under my variant does have one.
Rex Fernando
CC BY-SA 3.0
2014-05-11T22:45:08.900Z
Can you provide an example (or formally define the *Input* and *Question* of your problem)? (probably I didn't understand well the problem). P.S. note that in my comment $M$ is not the solution, but the set of triples+pairs given as input (like in the G&J 3DM formulation, in which $M$ is the set of input triples)
Marzio De Biasi
CC BY-SA 3.0
2014-05-11T23:42:05.553Z
I just realized, I wasn't formulating my problem correctly. I've fixed my question and hopefully made it more clear.
Rex Fernando
CC BY-SA 3.0
2014-05-13T05:22:35.310Z
Just to make sure I understand - you have both 2D matches and 3D matches in the same matching?
R B
CC BY-SA 3.0
2014-05-13T22:05:00.663Z
Yes, although which 2d matches you can add are limited.
Rex Fernando
<graph-algorithms><np-hardness><hypergraphs>
Hardness of 3-dimensional matching variant
Rex Fernando
# Hardness of 3-dimensional matching variant

(Asked by: username_0 on 2014-05-11)

I am thinking about a variant of 3-dimensional matching. In normal 3d matching, we have three sets of vertices $X$, $Y$ and $Z$, and a set of edges $E \subseteq X \times Y \times Z$. We want to choose a matching $M \subseteq E$ of maximum size.

I would like to instead choose $M$ from the set $E \cup \{(x,w) \bigm| \exists z: (x,w,z) \in E \vee \exists y: (x,y,w) \in E\}$. So for each triple in $E$, assume that choosing a pair with the first and second elements or a pair with the first and third elements to be part of $M$ would also be acceptable. (Note that a pair with the second and third elements is not allowed.) The question is if there a matching $M$ that covers every element in $X \cup Y \cup Z$ exactly once.

I was wondering whether this problem is still hard. The Garey & Johnson proof of NP-hardness of 3d matching seems to break down; if $M$ is chosen as specified above, the gadget for the variable doesn't work anymore.

**Tags:** graph-algorithms, np-hardness, hypergraphs
> **Comments:**
> **username_1**: Your problem is a generalization of 3DM (so it is still NPC): given an instance of 3DM, just pick the same M (i.e. $M \cap (W \times X) = M \cap (W \times Y) = \emptyset$) and you get an instance of your variant that has a solution iif the original 3DM instance has a solution.  
> **username_0**: The problem is that there are instances of 3DM that don't have a solution but where the corresponding instance under my variant does have one.  
> **username_1**: Can you provide an example (or formally define the *Input* and *Question* of your problem)? (probably I didn't understand well the problem). P.S. note that in my comment $M$ is not the solution, but the set of triples+pairs given as input (like in the G&J 3DM formulation, in which $M$ is the set of input triples)  
> **username_0**: I just realized, I wasn't formulating my problem correctly. I've fixed my question and hopefully made it more clear.  
> **username_2**: Just to make sure I understand - you have both 2D matches and 3D matches in the same matching?  
> **username_0**: Yes, although which 2d matches you can add are limited.  

---

## 1 answers

### Answer by username_1 on 2014-05-12. Score: 2 | Accepted answer

**EDIT (Aug 1):**

I posted a small report with a more detailed proof [on my blog](http://www.nearly42.org/npc-pills/npc-pill-003/); the reduction idea is the same, but the "gadget" used are better explained (you can also directly [download the pdf from here](http://www.nearly42.org/vdisk/pills/3dmvariant.pdf))

---

The problem seems NP-complete and this is a possible reduction from SET COVER.

Suppose you have an universe $A$ of $n$ elements: $A = \{a\_1,...,a\_n\}$, a collection of $m$ subsets $\mathcal{S} = \{S\_1,S\_2,...,S\_m\}$ (with $S\_i \subseteq A$) and an integer $k$. The SET COVER problem asks for a sub-collection $\mathcal{C} \subseteq \mathcal{S}$ of size at most $k$ such that $\bigcup\_{S\_i \in \mathcal{C}} S\_i = A$ (with $|\mathcal{C}| \leq k$).

The reduction to your problem (I call it 3DM-relaxed, 3DMR) can be done in the following way.

The subsets $S\_i$ are simulated using one or more elements of the set $X$, the elements of the universe $A$ are simulated using elements of the sets $Y$ and $Z$ ($a\_{2j}$ is simulated with an element $y\_{a\_{2j-1}}$ of $Y$, $a\_{2j-1}$ is simulated with an element $z\_{a\_{2j}}$ of $Z$).

We start with $X = \{ e\_1,e\_2,...,e\_{k} \}$ that will force the $|\mathcal{C}|=k$ constraint.

Then, for every subset $S\_i$ we create the triple: $(x^1\_{S\_i}, y\_{S\_i}, dum)$, where $dum$ is a new element of $Z$; and add the $k$ triples:  
  
$(e\_1,y\_{S\_i}, dum),(e\_2,y\_{S\_i}, dum),...,(e\_{k},y\_{S\_i}, dum)$

Note that *all* $dum$ elements are distinct!

In this way **at most** $k$ of the $x^1\_{S\_i}$ will be "free" to cover the elements representing the $a\_j$: indeed the $(e,\cdot,\cdot)$ triples can include at most $k$ of the $y\_{S\_i}$, the remaining $m-k$ must be included by the corresponding $(x^1\_{S\_i},\cdot,\cdot)$ triple.

To link the $x^1\_{S\_i}$ to the elements $y\_{a\_{2j}}, z\_{a\_{2j-1}}$ that correspond to the elements of the universe in $S\_i$, we add three *bridge* triples:  
$(x^1\_{S\_i},y\_{B\_i},z\_{B\_i})$,  
$(x^2\_{S\_i},y\_{B\_i},dum)$,  
$(x^3\_{S\_i},dum,z\_{B\_i})$

At this point the elements of $A$ can be linked to $x^2\_{S\_i}$ and $x^3\_{S\_i}$ (or we can further extend the capacity of $S\_i$ adding more bridge triples).

For example adding the triples:

$(x^2\_{S\_i},y\_{a\_2},z\_{a\_1}), (x^3\_{S\_i},y\_{a\_4},z\_{a\_3})$ we simulate the set: $S\_i = \{ a\_1, a\_2, a\_3, a\_4\}$.

The fundamental point is that if $x^1\_{S\_i}$ is "used" to cover the element $y\_{S\_i}$ (blue edges in the figure) then:

* $x^2\_{S\_i}$ *must* be used to include element $y\_{B\_i}$ and cannot be used to include elements $y\_{a\_2}, z\_{a\_1}$ (red edges in the figure);
* $x^3\_{S\_i}$ *must* be used to include element $z\_{B\_i}$ and cannot be used to include elements $y\_{a\_4}, z\_{a\_3}$ (red edges in the figure).

Some of the $S\_i$ included in the cover can have a non-empty intersection; so we must be sure that two distinct $x^p\_{S\_i}, x^q\_{S\_j}$ that are linked to the same element $a\_i$ (i.e. we have the triples $(x^p\_{S\_i}, a\_i, \cdot), (x^q\_{S\_j}, a\_i, \cdot)$) can be included in the matching. For this purpouse for every $x^p, p > 1$ we add a triple with two dum elements: $(x^p, dum, dum)$ (green edges in the figure below).

Finally we can add as many distinct triples $(x, y, dum\_i), (x, dum\_j, z)$ as needed to be able to *garbage collect* all the dum elements $dum\_i \in Z$ and the dum elements $dum\_j \in Y$ (otherwise the would not be included in the matching) if they are left alone.

Also note that if there are too many $S\_i$, the elements $e\_i$ can be included in the matching using their $z\_{dum}$ element in $Z$ (only the pair $(e\_i, z\_{dum})$ is picked).

The resulting 3DMR instance has a solution if and only if there is an set cover $\mathcal{C}$ of $A$ of size at most $k$.

![enter image description here](https://i.sstatic.net/aUH2F.png)

In the figure a triple $(x,y,z)$ is represented with two edges $(x,y),(x,z)$ of the same color. As an example, if $x^1\_{S\_1}$ corresponding to $S\_1 = \{a\_1,a\_2,a\_3,a\_4\}$, must be used to include $y\_{S\_1}$ (blue edges), then it cannot be used to include the elements $z\_{a\_1},y\_{a\_2},z\_{a\_3},y\_{a\_4}$ (red edges).

> **Comments:**
> **username_0**: I'm pretty sure that your transformation would result in solutions that aren't valid in the original graph (as long as we are thinking of the same problem; maybe my description still isn't right?). For instance if the original graph contains only the edges $(x,y_1,z_1)$ and $(x,y_2,z_2)$ then the new graph will allow a solution containing both $(x,y_1)$ and $(x'',z_2)$ which would correspond to a nonexistent edge $(x,y_1,z_2)$.  
> **username_1**: @RexFernando: mmm ... perhaps you're right ... but the 2DM solution must also contain $y_2$ and $z_1$ which seems not possible (i.e. $M' = \{(x,y_1),(x'',z_2)\}$ is not a valid solution for the 2DM) ... can you show a full example of non-working instance. Meanwhile I'll think more about the correctness of my proof.  
> **username_1**: You were right; perhaps I found a NP-hardness reduction. But it's a little bit complex, so perhaps it needs fixes (or simply it is wrong :-). Let me know.  
> **username_1**: @RexFernando: did you check the reduction? If it is correct and the problem is not known, we could write a small report.  
> **username_0**: Just saw your post, I will check it and get back to you.  
> **username_1**: @RexFernando: did you check it (or do you need clarifications)?  
> **username_0**: Can I get back to you next week? I took a quick look at it but it seems pretty involved, and i am on vacation now.  

---

