2024/08/07 by Andreas Björklund, Björklund, Andreas, Thore Husfeldt +1
Computer Science · #Advanced Multi-Objective Optimization Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2408.03699
openalex publication_date 2024/08/07 · openalex created_date 2024/10/23 · openalex updated_date 2026/07/28
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.731kpoly(n) time, improving over the 2kpoly(n) time algorithm by [Fomin et al., TALG 2024], but not the more recent 1.657kpoly(n) time algorithm by [Eiben, Koana, and Wahlström, SODA 2024]. When the graph is bipartite, we can solve the problem in 2k/2poly(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.