0
$\begingroup$

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!

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – domotorp
    Jul 29 '21 at 15:11
  • 2
    $\begingroup$ This question was asked and answered on the math stackexchange, see: math.stackexchange.com/questions/4212038/… $\endgroup$
    – Louis
    Jul 30 '21 at 7:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.