# Long Cycle in Bounded Tree-Width Graphs using DFS and Dynamic Programming

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 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 suggests an $O(k!2^kn)$-time algorithm based on depth-first search (DFS) and dynamic programming.

• Note that by now we know much faster algorithms for finding long cycles parametrized by treewidth and pathwidth: See arxiv.org/abs/1211.1505 for deterministic algorithms (there are faster randomized ones, see references within that paper). – Andreas Björklund May 31 '13 at 7:19
• 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 May 31 '13 at 16:40
• 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 Jun 2 '13 at 6:41

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: