A polynomial-time algorithm to determine (almost) Hamiltonicity of dense regular graphs

DOI10.1137/20M1356191MaRDI QIDQ5084096zbMATH OpenOpenAlexFDO

Authors Viresh Patel, Fabian Stroh

Publication date 23 June 2022

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph algorithmgraph partitioningHamilton cyclerobust expander

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Density (toughness, etc.) (05C42) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We give a polynomial-time algorithm for detecting very long cycles in dense regular graphs. Specifically, we show that, given $alphain(0,1)$, there exists a $c=c(alpha)$ such that the following holds: there is a polynomial-time algorithm that, given a $D$-regular graph $G$ on $n$ vertices with $Dgeqalphan$, determines whether $G$ contains a cycle on at least $n-c$ vertices. The problem becomes NP-complete if we drop either the density or the regularity condition. The algorithm combines tools from extremal graph theory and spectral partitioning as well as some further algorithmic ingredients.

Recommendations

• Finding Hamilton cycles in sparse random graphs
• Generating and Counting Hamilton Cycles in Random Regular Graphs
• Computational complexity of the Hamiltonian cycle problem in dense hypergraphs
• Finding large cycles in Hamiltonian graphs
• A fast parallel algorithm for finding Hamiltonian cycles in dense graphs

Cites work

• scientific article; zbMATH DE number 3902690 (Why is no real title available?)
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1263204 (Why is no real title available?)
• scientific article; zbMATH DE number 2119646 (Why is no real title available?)
• A proof of Sumner's universal tournament conjecture for large tournaments
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Dominating cycles in regular 3-connected graphs
• Eigenvalues and expanders
• Finding Hamilton cycles in robustly expanding digraphs
• Hamilton cycles in regular 2-connected graphs
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• Hamilton decompositions of regular expanders: applications
• Max cut and the smallest eigenvalue
• Minimizing the number of triangular edges
• On the approximation hardness of dense TSP and other path problems
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• Proof of the 1-factorization and Hamilton Decomposition Conjectures
• Solution to a problem of Bollobás and Häggkvist on Hamilton cycles in regular graphs
• Some Theorems on Abstract Graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete
• The robust component structure of dense regular graphs and applications

Cited in

(4)

• Hamilton cycles in dense regular digraphs and oriented graphs
• Parameterized algorithms in smooth 4-regular Hamiltonian graphs
• scientific article; zbMATH DE number 6004865 (Why is no real title available?)
• A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs

This page was built for publication: A polynomial-time algorithm to determine (almost) Hamiltonicity of dense regular graphs

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