Polynomial-time perfect matchings in dense hypergraphs

DOI10.1016/J.AIM.2014.10.009zbMATH Open1303.05155OpenAlexW2047917450MaRDI QIDQ475264FDOQ475264

Authors Peter Keevash, Fiachra Knox, Richard Mycroft

Publication date 26 November 2014

Published in Advances in Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.2608

zbMATH Keywords

algorithmshypergraphsmatchings

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Density (toughness, etc.) (05C42) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: 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.

Recommendations

• Polynomial-time perfect matchings in dense hypergraphs
• Decision problem for perfect matchings in dense \(k\)-uniform hypergraphs
• The complexity of perfect matchings and packings in dense hypergraphs
• Perfect matchings in uniform hypergraphs with large minimum degree
• The Complexity of Perfect Matching Problems on Dense Hypergraphs

Cites work

• scientific article; zbMATH DE number 3478938 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• A course in combinatorics.
• Computational complexity of the perfect matching problem in hypergraphs with subcritical density
• Decision problem for perfect matchings in dense \(k\)-uniform hypergraphs
• Degrees giving independent edges in a hypergraph
• Dirac-type questions for hypergraphs -- a survey (or more problems for Endre to solve)
• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs
• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs. II
• Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
• Limit Theorems for the Number of Empty Cells in an Equiprobable Scheme for Group Allocation of Particles
• Matchings in 3-uniform hypergraphs
• Matchings in hypergraphs of large minimum degree
• On perfect matchings in uniform hypergraphs with large minimum vertex degree
• Paths, Trees, and Flowers
• Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees
• Perfect matchings and \(K_4^3\)-tilings in hypergraphs of large codegree
• Perfect matchings in 3-partite 3-uniform hypergraphs
• Perfect matchings in 3-uniform hypergraphs with large vertex degree
• Perfect matchings in 4-uniform hypergraphs
• Perfect matchings in \(r\)-partite \(r\)-graphs
• Perfect matchings in large uniform hypergraphs with large minimum collective degree
• Polynomial-time perfect matchings in dense hypergraphs
• Reducibility among combinatorial problems
• Regularity lemmas for hypergraphs and quasi-randomness
• Santa Claus Meets Hypergraph Matchings
• Some Theorems on Abstract Graphs
• The Factorization of Linear Graphs
• The complexity of almost perfect matchings and other packing problems in uniform hypergraphs with high codegree
• The complexity of almost perfect matchings in uniform hypergraphs with high codegree
• Tight co-degree condition for perfect matchings in 4-graphs

Cited in

(12)

• The complexity of perfect packings in dense graphs
• Polynomial-time perfect matchings in dense hypergraphs
• Decision problem for perfect matchings in dense \(k\)-uniform hypergraphs
• The complexity of perfect matchings and packings in dense hypergraphs
• Embedding clique-factors in graphs with low \(\ell\)-independence number
• Packing \(k\)-partite \(k\)-uniform hypergraphs
• Graph Tilings in Incompatibility Systems
• On perfect matchings and tilings in uniform hypergraphs
• Hamilton cycles in hypergraphs below the Dirac threshold
• Cyclic triangle factors in regular tournaments
• Near Perfect Matchings in ${k}$-Uniform Hypergraphs II
• The Complexity of Perfect Matching Problems on Dense Hypergraphs

This page was built for publication: Polynomial-time perfect matchings in dense hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q475264)