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.

  • 2
    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
  • 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) – 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
  • 1
    Yes, although which 2d matches you can add are limited. – Rex Fernando May 13 '14 at 22:05
up vote 2 down vote accepted

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

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

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.