Finding longer cycles via shortest colourful cycle

Abstract

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/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.

Add reference to Eiben, Koana, and Wahlström, Determinantal Sieving, SODA 2024, that subsumes our main result and predates our paper