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

DOI10.1137/20M1356191zbMATH Open1491.05120arXiv2007.14502OpenAlexW3045552448MaRDI QIDQ5084096FDOQ5084096

Authors: Viresh Patel, Fabian Stroh 

Publication date: 23 June 2022

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

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.

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

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

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)

Cites Work

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

Cited In (4)

• Hamilton cycles in dense regular digraphs and oriented graphs
• Parameterized algorithms in smooth 4-regular Hamiltonian graphs
• Title not available (Why is that?)
• 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)