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 -