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

Question

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.

Answer 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 Andreas Björklund 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.