# 3-Dimensional Matching with at Most $2n$ Hyperedges

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

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$$.
• 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. – zdm87 Nov 23 '19 at 15:34
• @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$. – xskxzr Nov 24 '19 at 6:53