<p>There is a nice trick to reduce $\geq k$ cycle to finding a cycle of length exactly $t$, for $t \leq 2k$ (I first heard of this trick from Daniel Marx). The key observasjon is that contracting an edge of $G$ may not increase the length of the longest cycle in G, and may only decrease the length by a factor at most two. Thus we can search for cycles of length exactly $t$ for $k \leq t \leq 2k$. If no cycle is found, contract an edge and repeat.</p>

<p>This shoukd be quite a bit faster than the treewidth based algorithms, I believe, especially if you use the sieving methods for finding t-cycles (paths). There are very efficient implementations for $k$-path by Bjorklund et al:</p>

<p>Fast Witness Extraction Using a Decision Oracle, with Andreas Björklund and Petteri Kaski 
Proc. 22th Annual European Symposium on Algorithms (ESA 2014), LNCS 8737, 2014, pp. 149-160. </p>

<p>This should be adaptable to your problem.</p>

CC BY-SA 3.0
2014-11-12T21:47:39.343Z
2014-11-12T21:47:39.343Z
daniello
<p>For fixed parameter $k$, I would like to find a long cycle of length $\geq k$ in an undirected graph $G(V,E)$.  This can be done in $O(k!2^k|V|)$-time [2] using 1) depth-first search (DFS) and 2) dynamic programming on a bounded tree-width decomposition of $G$ derived from the DFS traversal.  </p>

<p>However, [2] does not contain explicit details on what information should be stored in the tables associated with each bag of the tree decomposition.  </p>

<blockquote>
  <p>When looking for long cycles using the dynamic programming method suggested by [2], are there any ideas or resources that specify what information needs to be stored at each bag and how to combine such tables?  </p>
</blockquote>

<p>References:</p>

<p>[1] <a href="http://dl.acm.org/citation.cfm?id=1328918">Gabow &amp; Nie, 2008</a>
contains an overview of the above problem, from the perspective of directed and undirected graphs, and includes a review of research on the undirected case.  </p>

<p>[2] <a href="http://dl.acm.org/citation.cfm?id=155609">Bodlaender, 1993</a> suggests an $O(k!2^kn)$-time algorithm based on depth-first search (DFS) and dynamic programming.</p>

CC BY-SA 3.0
2013-05-31T07:19:57.027Z
Note that by now we know much faster algorithms for finding long cycles parametrized by treewidth and pathwidth: See http://arxiv.org/abs/1211.1505 for deterministic algorithms (there are faster randomized ones, see references within that paper).
Andreas Björklund
CC BY-SA 3.0
2013-05-31T16:40:33.613Z
Thanks for the references, I hadn't seen these before and I'll take a look.  Overall, I'm trying to find the right balance between runtime and ease of understanding/implementing.
Jeff Wildman
CC BY-SA 3.0
2013-06-02T06:41:28.847Z
The randomized algorithm based on color coding are quite easy to implement so you should check them out. Refs in the paper that Andreas mentioned.
Chandra Chekuri
<graph-algorithms><treewidth><dynamic-programming>
Long Cycle in Bounded Tree-Width Graphs using DFS and Dynamic Programming
Jeff Wildman
# Long Cycle in Bounded Tree-Width Graphs using DFS and Dynamic Programming

(Asked by: username_0 on 2013-05-30)

For fixed parameter $k$, I would like to find a long cycle of length $\geq k$ in an undirected graph $G(V,E)$. This can be done in $O(k!2^k|V|)$-time [2] using 1) depth-first search (DFS) and 2) dynamic programming on a bounded tree-width decomposition of $G$ derived from the DFS traversal.

However, [2] does not contain explicit details on what information should be stored in the tables associated with each bag of the tree decomposition.

> When looking for long cycles using the dynamic programming method suggested by [2], are there any ideas or resources that specify what information needs to be stored at each bag and how to combine such tables?

References:

[1] [Gabow & Nie, 2008](http://dl.acm.org/citation.cfm?id=1328918)
contains an overview of the above problem, from the perspective of directed and undirected graphs, and includes a review of research on the undirected case.

[2] [Bodlaender, 1993](http://dl.acm.org/citation.cfm?id=155609) suggests an $O(k!2^kn)$-time algorithm based on depth-first search (DFS) and dynamic programming.

**Tags:** graph-algorithms, treewidth, dynamic-programming

> **Comments:**
> **username_1**: Note that by now we know much faster algorithms for finding long cycles parametrized by treewidth and pathwidth: See http://arxiv.org/abs/1211.1505 for deterministic algorithms (there are faster randomized ones, see references within that paper).  
> **username_0**: Thanks for the references, I hadn't seen these before and I'll take a look.  Overall, I'm trying to find the right balance between runtime and ease of understanding/implementing.  
> **username_2**: The randomized algorithm based on color coding are quite easy to implement so you should check them out. Refs in the paper that Andreas mentioned.  

---

## 1 answers

### Answer by username_3 on 2014-11-12. Score: 1

There is a nice trick to reduce $\geq k$ cycle to finding a cycle of length exactly $t$, for $t \leq 2k$ (I first heard of this trick from Daniel Marx). The key observasjon is that contracting an edge of $G$ may not increase the length of the longest cycle in G, and may only decrease the length by a factor at most two. Thus we can search for cycles of length exactly $t$ for $k \leq t \leq 2k$. If no cycle is found, contract an edge and repeat.

This shoukd be quite a bit faster than the treewidth based algorithms, I believe, especially if you use the sieving methods for finding t-cycles (paths). There are very efficient implementations for $k$-path by Bjorklund et al:

Fast Witness Extraction Using a Decision Oracle, with username_1 and Petteri Kaski
Proc. 22th Annual European Symposium on Algorithms (ESA 2014), LNCS 8737, 2014, pp. 149-160.

This should be adaptable to your problem.


---

