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

Question

Let $p\geq 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!

Answer 1

We (a3nm and I) noticed that the case of $p\leq 2$ is trivial and the case $p=3$ is known as 3-dimensional matching which is an NP-complete problem (even when asking only for a matching covering all nodes).

Note that your problem slightly differ because you fix $|E|=n\times (p-1)$ and also because you might have $p>3$. Here is the sketch idea to take care of those two problems.

Start from an instance of a perfect 3-dimensional matching with the sets $V_1 \dots V_3$ of $k$ nodes and the set $E$ of edges, now if there are too much edges in $E$, you can add a new node $v_i$ into $V_i$ plus an edge $(v_1, \dots, v_p)$ and repeat this process until $E$ is big enough. If there are too few edges, you still add one node $v_i$ in each $V_i$ and one edge $(v_1, \dots, v_p)$ but you can also add lots of edges of the form $(v_1,w_2, \dots, w_p)$ where the $w_i$ are taken from the $V_i$. Because the original instance had $n\leq |E| \leq n^3$ this reduction is polynomial. And it is easy to see that there is a perfect matching iff the original had one (the added node can only be matched with the edge for them).

For the case $p>3$ the hardness can be shown from the case of $p=3$. Take a hard instance for the case $p=3$, then set $V_i = \{ x^i | x \in V_3\}$ for $i>3$ and the edges will be changed from $(v_1, v_2, v_3)$ to $(v_1, v_2,v_3,v^4_3, \dots, v^{p}_3)$. Then you need to add edges because $E$ is not large but you can use the technique shown above. This work for any fixed $p$ and any $p$ polynomial in $n$.

I have not investigated what happens when $p$ is much bigger than $n$ beside the obvious $O(|E|^{|V|})$ algorithm which prohibits the NP-completeness when $n$ is fixed but there might be something interesting there :)