2
$\begingroup$

In 3 dimensional matching, we are given a set $M\subseteq X\times Y\times Z$ where $|X|=|Y|=|Z|=n$. A matching in $M$ is a subset $T⊆M$ such that no elements in $T$ agree in any coordinate. The goal is to find a matching in $M$ of size $n$.

If we assume that $n\leq|M|=m<2n$, can we solve 3DM in polynomial-time?

I know that in a 2-bounded instance of 3DM, 3DM can be solved in polynomial-time. The 2-bounded instance is when no element appears in more than two triples in $M$. For $m<2n$, we do not necessarily have a 2-bounded instance.

Further, in a 3-bounded instance of 3DM, 3DM is NP-hard. The 3-bounded instance is when no element appears in more than three triples in $M$, that is $m\leq3n$.

$\endgroup$
4
$\begingroup$

The restriction $m < 2n$ does not help to solve the problem in polynomial time. Note that any 3-dimensional matching instance can be polynomially reduced into an instance with $m < 2n$ by adding $m$ elements to the sets $X$, $Y$ and $Z$ and $m$ hyperedges to connect these new elements. The resulting instance has $n' = n + m$ and $m' = 2m$, so $m' < 2n'$ assuming $n>0$. Also, this reduction can be generalized for any constant $c > 1$ to show that 3-dimensional matching is NP-complete with the restriction that $m < cn$.

For solving the problem faster I suggest to find some other restrictions in the instances you have. For example in graphs, the natural parameter to express sparseness would be degeneracy.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Do you mean each set will have $m+n$ elements? And no hyperedges are added? I think that if $m\leq n$, then we can solve 3DM easily, but your reduction seems to work too, weird. $\endgroup$ – zdm87 Nov 23 '19 at 15:34
  • 3
    $\begingroup$ @zdm87 The reduction should also add $m$ tuples into $M$ for the $3m$ new elements, so it does not work for $m\le n$, but works for $n\le m<2n$. $\endgroup$ – xskxzr Nov 24 '19 at 6:53
  • $\begingroup$ Sorry, I first though you were looking for a maximum matching not a perfect matching. As @xskxzr mentioned, the same idea works for perfect matching too. I'll edit my answer. $\endgroup$ – Laakeri Nov 24 '19 at 10:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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