Finding matchings in dense hypergraphs

MaRDI QIDQ6414812zbMATH OpenFDO

Authors Jie Han, Peter Keevash

Publication date 23 October 2022

Abstract: We consider the algorithmic decision problem that takes as input an $n$-vertex $k$-uniform hypergraph $H$ with minimum codegree at least $m-c$ and decides whether it has a matching of size $m$. We show that this decision problem is fixed parameter tractable with respect to $c$. Furthermore, our algorithm not only decides the problem, but actually either finds a matching of size $m$ or a certificate that no such matching exists. In particular, when $m=n/k$ and $c=O(logn)$, this gives a polynomial-time algorithm, that given any $n$-vertex $k$-uniform hypergraph $H$ with minimum codegree at least $n/k-c$, finds either a perfect matching in $H$ or a certificate that no perfect matching exists.

This page was built for publication: Finding matchings in dense hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6414812)