5
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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). $\endgroup$ – Andreas Björklund May 31 '13 at 7:19
  • $\begingroup$ 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. $\endgroup$ – Jeff Wildman May 31 '13 at 16:40
  • $\begingroup$ 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. $\endgroup$ – Chandra Chekuri Jun 2 '13 at 6:41
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.