Finding longer cycles via shortest colourful cycle

We consider the parameterised $k,e$-Long Cycle problem, in which you are given an $n$-vertex undirected graph $G$, a specified edge $e$ in $G$, and a positive integer $k$, and are asked to decide if the graph $G$ has a simple cycle through $e$ of length at least $k$. We show how to solve the problem in ${1.731}^k\mathrm{poly}(n)$ time, improving over the $2^k\mathrm{poly}(n)$ time algorithm by [Fomin et al., TALG 2024], but not the more recent ${1.657}^k\mathrm{poly}(n)$ time algorithm by [Eiben, Koana, and Wahlström, SODA 2024]. When the graph is bipartite, we can solve the problem in $2^{k\mathrm{/}2}\mathrm{poly}(n)$ time, matching the fastest known algorithm for finding a cycle of length exactly $k$ in an undirected bipartite graph [Björklund et al., JCSS 2017]. Our results follow the approach taken by [Fomin et al., TALG 2024], which describes an efficient algorithm for finding cycles using many colours in a vertex-coloured undirected graph. Our contribution is twofold. First, we describe a new algorithm and analysis for the central colourful cycle problem, with the aim of providing a comparatively short and self-contained proof of correctness. Second, we give tighter reductions from $k,e$-Long Cycle to the colourful cycle problem, which lead to our improved running times.