$G$.[^1] They also show one cannot replace $(\frac{\alpha}{1 - \alpha})$ with $(1 - \varepsilon_0(1-2\alpha))$ where $\varepsilon_0 = 1/742$ unless $P = NP$. The two algorithms are not directly comparable: while theirs works on all dense graphs, ours achieves a much better approximation ratio for dense regular Hamiltonian graphs. In Section \[sec:conc\], we discuss how our methods can be used for the longest cycle problem to achieve an approximation ratio very close to one for general dense regular graphs.

Our algorithm is inspired by questions and results about Hamiltonicity in extremal graph theory; here one is interested in various types of conditions that guarantee Hamiltonicity such as in Dirac’s theorem. There are two extremal examples that show $n/2$ is tight in Dirac’s theorem: a slightly imbalanced complete bipartite graph and a graph consisting of two disjoint cliques. One might hope to eliminate these barriers to Hamiltonicity by imposing some connectivity and regularity conditions. In this direction, Bollobás [@bollobasconj] and H[ä]{}ggkvist (see [@jackson1980hamilton]) independently conjectured that a $t$-connected regular graph with degree at least $n/(t+1)$ is Hamiltonian. Jackson [@jackson1980hamilton] proved the conjecture for $t=2$, while Jung [@Jung] and Jackson, Li, and Zhu [@JacksonLiZhu] gave an example showing the conjecture does not hold 