for $t \geq 4$. Finally, Kühn, Lo, Osthus, and Staden [@kuhn2014robust; @kuhn2016solution] resolved the conjecture by proving the case $t=3$ asymptotically. Although the conjecture does not hold in general, it suggests that questions of Hamiltonicity (and long cycles) might be easier in some sense for (dense) regular graphs, and our result seems to confirm this.

Our algorithm relies heavily on the notion of robust expansion, a notion of expansion for dense (directed) graphs introduced and applied by Kühn and Osthus together with several co-authors to resolve and make progress on a number of long-standing conjectures in extremal graph theory; see for example [@Rob0; @Rob2; @Rob4; @Robb2]. In particular, Kühn, Lo, Osthus and Staden [@kuhn2014robust; @kuhn2016solution], in their proof of the $t=3$ case of the Bollob[á]{}s-H[ä]{}ggkvist conjecture showed that all dense regular graphs have a vertex partition into a small number of parts where each part induces a (bipartite) robust expander. This decomposition is central to our algorithm, and by combining their argument with some spectral partitioning techniques, we are able to construct such a partition algorithmically in polynomial time; this may be of independent interest. A further by-product of this is that we can partially answer a question of K[ü]{}hn 