Article ID Journal Published Year Pages File Type
4665604 Advances in Mathematics 2015 70 Pages PDF
Abstract

Let H be a k-graph on n   vertices, with minimum codegree at least n/k+cnn/k+cn for some fixed c>0c>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ński, Ruciński and Szymańska; Szymańska previously showed that this problem is NP-hard for a minimum codegree of n/k−cnn/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.

Related Topics
Physical Sciences and Engineering Mathematics Mathematics (General)
Authors
, , ,