arXiv:2007.14502 [math.CO]AbstractReferencesReviewsResources
A polynomial-time algorithm to determine (almost) Hamiltonicity of dense regular graphs
Published 2020-07-28Version 1
We give a polynomial-time algorithm for detecting very long cycles in dense regular graphs. Specifically, we show that, given $\alpha \in (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 $D\geq \alpha n$, 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.
Comments: 35 pages, 3 figures
Related articles: Most relevant | Search more
arXiv:1409.3325 [math.CO] (Published 2014-09-11)
Solution to a problem on hamiltonicity of graphs under Ore- and Fan-type heavy subgraph conditions
arXiv:1407.4845 [math.CO] (Published 2014-07-17)
Hamiltonicity and $σ$-hypergraphs
Hamiltonicity of 3-arc graphs