Finding matchings in dense hypergraphs
share
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.
READ FULL TEXT