TY - CHAP
T1 - Polynomial-time perfect matchings in dense hypergraphs
AU - Keevash, Peter
AU - Knox, F.
AU - Mycroft, R.
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?eid=2-s2.0-84879817378&partnerID=8YFLogxK
U2 - 10.1145/2488608.2488647
DO - 10.1145/2488608.2488647
M3 - Chapter
AN - SCOPUS:84879817378
SN - 9781450320290
SP - 311
EP - 320
BT - Proceedings of the Annual ACM Symposium on Theory of Computing
ER -