Polynomial-time perfect matchings in dense hypergraphs

Peter Keevash, Fiachra Knox, Richard Mycroft

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)
230 Downloads (Pure)


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 Karpi\'nski, Ruci\'nski and Szyma\'nska; Szyma\'nska previously showed that this problem is NP-hard 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
Pages (from-to)265-334
Number of pages70
JournalAdvances in Mathematics
Early online date4 Nov 2014
Publication statusPublished - 10 Jan 2015


  • Hypergraphs
  • Algorithms
  • matchings


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

Cite this