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

Abstract

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\ge \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.

35 pages, 3 figures