3-Dimensional Matching with at Most $2n$ Hyperedges
The restriction $m &lt; 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 &lt; 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' &lt; 2n'$ assuming $n&gt;0$. Also, this reduction can be generalized for any constant $c &gt; 1$ to show that 3-dimensional matching is NP-complete with the restriction that $m &lt; 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.