---
abstract: '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.'
address: 'University of Amsterdam, Korteweg-de Vries Institute (KdVI), Amsterdam, The Netherlands.'
author:
- Viresh Patel and Fabian Stroh
bibliography:
- 'writeup.bib'
title: 'A polynomial-time algorithm to determine (almost) Hamiltonicity of dense regular graphs'
---

Introduction {#sec:intro}
============

The study of Hamilton cycles in graphs is a classical part of graph theory. It has been studied intensely from structural, extremal and algorithmic perspectives and is especially relevant due to its connection with the travelling salesman problem. A Hamilton cycle in a graph is a spanning cycle, i.e. a cycle that contains every vertex of a graph. This paper is concerned with the algorithmic question of determining 