The complexity of perfect matchings and packings in dense hypergraphs

DOI10.1016/J.JCTB.2019.06.004MaRDI QIDQ2284737zbMATH OpenOpenAlexWikidataFDO

Authors Jie Han, Andrew Treglown

Publication date 15 January 2020

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

absorbing methodcomplexityperfect matching

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Given two $k$-graphs $H$ and $F$, a perfect $F$-packing in $H$ is a collection of vertex-disjoint copies of $F$ in $H$ which together cover all the vertices in $H$. In the case when $F$ is a single edge, a perfect $F$-packing is simply a perfect matching. For a given fixed $F$, it is often the case that the decision problem whether an $n$-vertex $k$-graph $H$ contains a perfect $F$-packing is NP-complete. Indeed, if $kgeq3$, the corresponding problem for perfect matchings is NP-complete whilst if $k=2$ the problem is NP-complete in the case when $F$ has a component consisting of at least $3$ vertices. In this paper we give a general tool which can be used to determine classes of (hyper)graphs for which the corresponding decision problem for perfect $F$-packings is polynomial time solvable. We then give three applications of this tool: (i) Given $1leqellleqk-1$, we give a minimum $ell$-degree condition for which it is polynomial time solvable to determine whether a $k$-graph satisfying this condition has a perfect matching; (ii) Given any graph $F$ we give a minimum degree condition for which it is polynomial time solvable to determine whether a graph satisfying this condition has a perfect $F$-packing; (iii) We also prove a similar result for perfect $K$-packings in $k$-graphs where $K$ is a $k$-partite $k$-graph. For a range of values of $ell,k$ (i) resolves a conjecture of Keevash, Knox and Mycroft whilst (ii) answers a question of Yuster in the negative. In many cases our results are best possible in the sense that lowering the minimum degree condition means that the corresponding decision problem becomes NP-complete.

Recommendations

• The complexity of almost perfect matchings and other packing problems in uniform hypergraphs with high codegree
• The complexity of perfect packings in dense graphs
• The Complexity of Perfect Matching Problems on Dense Hypergraphs
• Polynomial-time perfect matchings in dense hypergraphs
• Polynomial-time perfect matchings in dense hypergraphs

Cites work

• K₄⁻‐factor in a graph
• \(F\)-factors in hypergraphs via absorption
• \(H\)-factors in dense graphs
• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• A fast algorithm for equitable coloring
• A note on perfect matchings in uniform hypergraphs
• Combinatorial and computational aspects of graph packing and graph decomposition
• Computational complexity of the perfect matching problem in hypergraphs with subcritical density
• Critical chromatic number and the complexity of perfect packings in graphs
• Decision problem for perfect matchings in dense k-uniform hypergraphs
• Dirac-type questions for hypergraphs -- a survey (or more problems for Endre to solve)
• Embedding large subgraphs into dense graphs
• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs
• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs. II
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
• Matchings in 3-uniform hypergraphs
• Matchings in hypergraphs of large minimum degree
• Maximum bounded \(H\)-matching is Max SNP-complete
• Near Perfect Matchings in ${k}$-Uniform Hypergraphs II
• On extremal problems of graphs and generalized graphs
• On perfect matchings in uniform hypergraphs with large minimum vertex degree
• On the Complexity of General Graph Factor Problems
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• Packing k-partite k-uniform hypergraphs
• Paths, Trees, and Flowers
• Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees
• Perfect matchings and K₄^3-tilings in hypergraphs of large codegree
• Perfect matchings in 3-uniform hypergraphs with large vertex degree
• Perfect matchings in 4-uniform hypergraphs
• Perfect matchings in hypergraphs and the Erdős matching conjecture
• Perfect matchings in large uniform hypergraphs with large minimum collective degree
• Perfect matchings in uniform hypergraphs with large minimum degree
• Perfect packings with complete graphs minus an edge
• Polynomial-time perfect matchings in dense hypergraphs
• Powers of tensors and fast matrix multiplication
• Proof of a tiling conjecture of Komlós
• Proof of the Alon-Yuster conjecture
• Recent advances on Dirac-type problems for hypergraphs
• Reducibility among combinatorial problems
• The complexity of almost perfect matchings and other packing problems in uniform hypergraphs with high codegree
• The complexity of perfect packings in dense graphs
• The Factorization of Linear Graphs
• The minimum degree threshold for perfect graph packings
• Tight co-degree condition for perfect matchings in 4-graphs
• Tiling Turán theorems

Cited in

(25)

• The complexity of almost perfect matchings and other packing problems in uniform hypergraphs with high codegree
• Codegree threshold for tiling balanced complete \(3\)-partite \(3\)-graphs and generalized \(4\)-cycles
• Tiling multipartite hypergraphs in quasi-random hypergraphs
• Perfect packings in quasirandom hypergraphs. I.
• The computational complexity of the edge-perfect graph and the totally balanced packing game recognition problems
• Decision problem for perfect matchings in dense k-uniform hypergraphs
• The complexity of perfect packings in dense graphs
• Computational complexity of the perfect matching problem in hypergraphs with subcritical density
• scientific article; zbMATH DE number 434914 (Why is no real title available?)
• The Complexity of Perfect Matching Problems on Dense Hypergraphs
• Packing $k$-Matchings and $k$-Critical Graphs
• On perfect matchings and tilings in uniform hypergraphs
• Polynomial-time perfect matchings in dense hypergraphs
• Matching of given sizes in hypergraphs
• Codegree conditions for tiling complete \(k\)-partite \(k\)-graphs and loose cycles
• Perfect Packings in Quasirandom Hypergraphs II
• Minimum codegree threshold for \(C_6^3\)-factors in 3-uniform hypergraphs
• Polynomial-time perfect matchings in dense hypergraphs
• Covering 3‐uniform hypergraphs by vertex‐disjoint tight paths
• Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
• FF‐factors in Quasi‐random Hypergraphs
• Cycle-factors in oriented graphs
• Non-linear Hamilton cycles in linear quasirandom and uniformly dense hypergraphs
• On the Keevash-Knox-Mycroft conjecture
• Matchings in multipartite hypergraphs

This page was built for publication: The complexity of perfect matchings and packings in dense hypergraphs

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