# Is p-dimensional matching with (p−1)n edges NP-hard? What about 3n edges?

Let $$p≥3$$ an integer. I am wondering whether or not the following problems are NP-hard or not (and if they are, I am looking for a convincing argument, or even better a detailed proof):

1. Let $$V_1,\dots,V_p$$ disjoint vertex sets each of size $$n$$. There are $$m=(p−1)n$$ edges $$E\subset V_1\times\dots\times V_p$$. Determine whether or not there exists a matching of size at least $$n$$ or not.

2. Let $$V_1,\dots,V_p$$ disjoint vertex sets each of size $$n$$. There are $$m=3n$$ edges $$E\subset V_1\times\dots\times V_p$$. Determine whether or not there exists a matching of size at least $$n$$ or not.

Thanks for the help!

• This won't make a difference, because those few edges might be essentially concentrated on a small part of the $V_i$'s. Imagine that there are $n-\sqrt n$ vertices in each $V_i$ covered by only one edge, with a unique matching on them, while the rest of the $p\sqrt n$ vertices have a complicated graph on them. Jul 29 '21 at 15:11
• This question was asked and answered on the math stackexchange, see: math.stackexchange.com/questions/4212038/… Jul 30 '21 at 7:43