Polynomial-time perfect matchings in dense hypergraphs

Peter Keevash, F. Knox, R. Mycroft

Research output: Chapter in Book/Report/Conference proceedingChapter

3 Citations (Scopus)


Let H be a k-graph on n vertices, with minimum codegree at least n/k + cn for some fixed c > 0. In this paper we construct a polynomial-time algorithm which finds either a perfect matching in H or a certificate that none exists. This essentially solves a problem of Karpínski, Rucínski and Szymánska, who previously showed that this problem is NPhard for a minimum codegree of n/k - cn. Our algorithm relies on a theoretical result of independent interest, in which we characterise any such hypergraph with no perfect matching using a family of lattice-based constructions.
Original languageEnglish
Title of host publicationProceedings of the Annual ACM Symposium on Theory of Computing
Number of pages10
Publication statusPublished - 2013


Dive into the research topics of 'Polynomial-time perfect matchings in dense hypergraphs'. Together they form a unique fingerprint.

Cite this