whether a graph contains an (almost) Hamilton cycle. The Hamiltonicity problem is NP-hard in general [@Garey], and so there is a lot of interest in understanding the problem for restricted graph classes. In this paper, we will focus on dense graphs, that is graphs in which the minimum degree is linear in the number of vertices.

Dirac’s theorem [@dirac1952some] guarantees the existence of a Hamilton cycle in any $n$-vertex graph of minimum degree at least $n/2$, so this immediately gives a (trivial) algorithm to determine existence in such graphs (and its proof also gives a polynomial-time algorithm for finding a Hamilton cycle). On the other hand, for each $\varepsilon>0$, the problem of determining Hamiltonicity in $n$-vertex graphs of minimum degree $(\frac{1}{2} - \varepsilon)n$ is NP-complete [@de1999approximation] (see also Proposition \[pr:hard\]). Our main result, given below, shows that the situation is quite different if we also insist the graphs are regular: we show that determining almost Hamiltonicity in dense regular graphs is polynomial-time solvable.

\[thm:main\] For every $\alpha\in(0,1]$, there exists $c = c(\alpha) = 100 \alpha^{-2}$ and a (deterministic) polynomial-time algorithm that, given an $n$-vertex $D$-regular graph $G$ with $D\geq \alpha n$ as input, determines whether $G$ contains a cycle on 