Finding Matchings in Dense Hypergraphs
Jie Han, Peter Keevash · ACM Transactions on Algorithms · 2025
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(\log n)\) , 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.