<p>Let <span class="math-container">$p≥3$</span> 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):</p>
<ol>
<li><p>Let <span class="math-container">$V_1,\dots,V_p$</span> disjoint vertex sets each of size <span class="math-container">$n$</span>. There are <span class="math-container">$m=(p−1)n$</span> edges <span class="math-container">$E\subset V_1\times\dots\times V_p$</span>. Determine whether or not there exists a matching of size at least <span class="math-container">$n$</span> or not.</p>
</li>
<li><p>Let <span class="math-container">$V_1,\dots,V_p$</span> disjoint vertex sets each of size <span class="math-container">$n$</span>. There are <span class="math-container">$m=3n$</span> edges <span class="math-container">$E\subset V_1\times\dots\times V_p$</span>. Determine whether or not there exists a matching of size at least <span class="math-container">$n$</span> or not.</p>
</li>
</ol>
<p>Thanks for the help!</p>

CC BY-SA 4.0
2021-07-29T15:11:35.033Z
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.
domotorp
CC BY-SA 4.0
2021-07-30T07:43:40.187Z
This question was asked and answered on the math stackexchange, see: https://math.stackexchange.com/questions/4212038/is-p-dimensional-matching-with-p-1n-edges-np-hard-what-about-3n-edges
Louis
<np-hardness><matching>
Is p-dimensional matching with (p−1)n edges NP-hard? What about 3n edges?
Ernie Vigelan
# Is p-dimensional matching with (p−1)n edges NP-hard? What about 3n edges?

(Asked by: username_0 on 2021-07-29)

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!

**Tags:** np-hardness, matching

> **Comments:**
> **username_1**: 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.  
> **username_2**: This question was asked and answered on the math stackexchange, see: https://math.stackexchange.com/questions/4212038/is-p-dimensional-matching-with-p-1n-edges-np-hard-what-about-3n-edges  

---

## 0 answers

