# Hardness of 3-dimensional matching variant

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.

• 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 May 11 '14 at 21:58
• 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 May 11 '14 at 22:26
• 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 May 11 '14 at 22:45
• I just realized, I wasn't formulating my problem correctly. I've fixed my question and hopefully made it more clear. – Rex Fernando May 11 '14 at 23:42
• Yes, although which 2d matches you can add are limited. – Rex Fernando May 13 '14 at 22:05

EDIT (Aug 1):

I posted a small report with a more detailed proof on my blog; the reduction idea is the same, but the "gadget" used are better explained (you can also directly download the pdf from here)

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).

$(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$.

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).

• 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 May 12 '14 at 1:30
• @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 May 12 '14 at 6:52
• 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 May 14 '14 at 15:01
• @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 May 16 '14 at 14:36
• Just saw your post, I will check it and get back to you. – Rex Fernando May 17 '14 at 5:16