  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.
