at least $n - c$ vertices. Furthermore there is a (randomised) polynomial-time algorithm to find such a cycle if it exists.

Note that the problem of determining the existence of a very long cycle (as in the result above) becomes NP-complete if we drop either the density or the regularity condition on $G$; see Proposition \[pr:hard\]. The question of whether Theorem \[thm:main\] holds for $c= c(\alpha) = 0$ (i.e. the Hamilton cycle problem) remains open and is discussed in Section \[sec:conc\]. Also, see Remark \[rem:runtime\] for a discussion of the explicit running time of the algorithm.

Arora, Karger, and Karpinski [@AroraSTOC; @Arora] initiated the systematic study of NP-hard problems on dense graphs and this continues to be an active area of research. The closest result to ours (to the best of our knowledge) is an approximation algorithm for the longest cycle problem in dense (not necessarily regular) graphs that is due to Csaba, Karpinski and Krysta [@Csaba2002Approx]. For each $\alpha \in (0, 1/2)$, they give a polynomial-time algorithm which, given an $n$-vertex graph $G$ of minimum degree $\alpha n$, finds a cycle of length at least $(\frac{\alpha}{1 - \alpha}) \ell$, where $\ell$ is the length of the longest cycle in 