FINDING MATCHINGS IN DENSE HYPERGRAPHS

NEW

Problem: Reconstructed statement: for fixed $k\ge3$ and fixed small rational $\varepsilon>0$, consider the promise decision problem whose input is a $k$-uniform hypergraph $H$ on disjoint sets $X\cup Y$, integers $c,t$, with

and with $H[Y]$ independent. Decide whether $H$ has a matching of size $t$.

This is the natural complexity-theoretic formalization of Han–Keevash Problem 6.1. The per-function version for prescribed $c(n),t(n)$ is more ambiguous; the uniform version has $c,t$ as part of the input.

Result: The problem is NP-complete for every fixed $k\ge3$. In fact, NP-hardness holds even with $c=o(t)$.

Proof. Membership in NP is immediate: a certificate is $t$ disjoint edges.

For NP-hardness reduce from $k$-dimensional matching with a distinguished part $A$, which is NP-complete for fixed $k\ge3$. Thus we are given a $k$-graph $G$ on $A\cup B$, every edge meeting $A$ in exactly one vertex, and an integer $q$, and ask whether $G$ has $q$ disjoint edges.

Choose $d=q^{2}$. Add a dummy set $U$ of size $d$. Choose $n$ polynomially large, with $\varepsilon n\in\mathbb Z$, so that

Let

where $P,Q$ are padding sets making $|X|=\varepsilon n$, $|Y|=n$.

Define $H$ by

Then $H[Y]$ is independent, since every edge either is an original edge meeting $A\subseteq X$, or meets $U\subseteq X$.

For every $(k-1)$-set $S$:

• if $S\cap U=\varnothing$, then $S\cup\{u\}\in E(H)$ for every $u\in U$, so $\deg_H(S)\ge d$;
• if $S\cap U\ne\varnothing$, then $S\cup\{v\}\in E(H)$ for every $v\notin S$, so again $\deg_H(S)\ge d$.

Set

Then $t-c=d$, so $\delta_{k-1}(H)\ge t-c$, and $c\le t\le |X|$.

Every added edge meets $U$, so any matching in $H$ uses at most $d$ added edges. The remaining edges are edges of $G$. Hence a matching of size $d+q$ in $H$ forces a matching of size at least $q$ in $G$.

Conversely, if $G$ has $q$ disjoint edges, extend them by $d$ disjoint added edges using the $d$ vertices of $U$ and $d(k-1)$ fresh padding vertices from $Q$. Thus $H$ has a matching of size $t=d+q$.

Therefore $H$ has a matching of size $t$ iff $G$ has a matching of size $q$. The reduction is polynomial for fixed $k$. Since $c/t=q/(q^{2}+q)\to0$, the hardness is not caused by the degenerate case $c=t$.

Thus the reconstructed uniform decision problem is NP-complete.

Citation: Base NP-completeness: R. M. Karp, “Reducibility among combinatorial problems,” 1972, where 3-dimensional matching is one of the original NP-complete problems.
Problem source: J. Han and P. Keevash, “Finding matchings in dense hypergraphs,” arXiv:2210.12643, Problem 6.1.