Polynomial-time perfect matchings in dense hypergraphs

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

Peter Keevash, Fiachra Knox, Richard Mycroft

Publication date: 26 November 2014

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reducibility among Combinatorial Problems
• A course in combinatorics.
• Paths, Trees, and Flowers
• The Factorization of Linear Graphs
• Some Theorems on Abstract Graphs
• Perfect matchings and \(K_4^3\)-tilings in hypergraphs of large codegree
• Perfect matchings in large uniform hypergraphs with large minimum collective degree
• Matchings in 3-uniform hypergraphs
• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs. II
• Perfect matchings in 3-uniform hypergraphs with large vertex degree
• On Perfect Matchings in Uniform Hypergraphs with Large Minimum Vertex Degree
• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs
• Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees
• Perfect matchings in 4-uniform hypergraphs
• Limit Theorems for the Number of Empty Cells in an Equiprobable Scheme for Group Allocation of Particles
• Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
• Polynomial-time perfect matchings in dense hypergraphs
• Perfect matchings in \(r\)-partite \(r\)-graphs
• Degrees giving independent edges in a hypergraph
• Perfect matchings in 3-partite 3-uniform hypergraphs
• Tight co-degree condition for perfect matchings in 4-graphs
• Matchings in hypergraphs of large minimum degree
• The complexity of almost perfect matchings and other packing problems in uniform hypergraphs with high codegree
• Decision problem for perfect matchings in dense 𝑘-uniform hypergraphs
• COMPUTATIONAL COMPLEXITY OF THE PERFECT MATCHING PROBLEM IN HYPERGRAPHS WITH SUBCRITICAL DENSITY
• Santa Claus Meets Hypergraph Matchings
• The Complexity of Almost Perfect Matchings in Uniform Hypergraphs with High Codegree
• Regularity lemmas for hypergraphs and quasi-randomness

Cited In (11)

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

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)