Finding longer cycles via shortest colourful cycle
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929458927108096 |
|---|---|
| author | Björklund, Andreas Husfeldt, Thore |
| author_facet | Björklund, Andreas Husfeldt, Thore |
| contents | 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\operatorname{poly}(n)$ time, improving over the $2^k\operatorname{poly}(n)$ time algorithm by [Fomin et al., TALG 2024], but not the more recent $1.657^k\operatorname{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}\operatorname{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_03699 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Finding longer cycles via shortest colourful cycle Björklund, Andreas Husfeldt, Thore Data Structures and Algorithms 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\operatorname{poly}(n)$ time, improving over the $2^k\operatorname{poly}(n)$ time algorithm by [Fomin et al., TALG 2024], but not the more recent $1.657^k\operatorname{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}\operatorname{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. |
| title | Finding longer cycles via shortest colourful cycle |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2408.03699 |