4
$\begingroup$

I'm looking for an algorithm that solves the Hamiltonian cycle problem parameterized by treewidth. In particular, I'm curious about such an algorithm running in $\text{tw}(G)^{O(\text{tw}(G))} \cdot n$ time.

In other words, once you have the treewidth, an algorithm that says if the input graph has a Hamiltonian cycle.

$\endgroup$
  • 1
    $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Jun 6 '16 at 18:20
8
$\begingroup$

If you want an FPT algorithm for the problem (parameterized by treewidth $t$), you want an algorithm working in time $f(t) \cdot n^{O(1)}$, where $f$ is any computable function (depending solely on $t$). Of course, it would be nice to make $f$ as appealing as possible.

In addition to the mentioned algorithm running in $O(t^t n)$ time, you can also get a faster (randomized) algorithm using the Cut'n'Count technique of Cygan et al. [1]. In particular, you get an algorithm running in time $4^t n^{O(1)}$. It is also possible to get a deterministic algorithm working in $c^t n^{O(1)}$ (for some small constant $c$) using a rank-based approach of [2].


[1] Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J. M., & Wojtaszczyk, J. O. "Solving connectivity problems parameterized by treewidth in single exponential time." IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), 2011.

[2] Bodlaender, H. L., Cygan, M., Kratsch, S., & Nederlof, J. "Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth." Automata, Languages, and Programming. Springer Berlin Heidelberg, 2013. 196-207.

$\endgroup$
5
$\begingroup$

There is an outline of the algorithm you want in these slides: http://www.cs.bme.hu/~dmarx/papers/marx-warsaw-fpt2. Given a nice-tree decomposition of width $w$ for $G$, the algorithm runs in time $O(w^w \cdot n)$. As it is based on a nice-tree decomposition, you will need to show what happens in the case of a forget node, an introduce node, and a join node when added to the solution of a smaller sub-problem. These details can be found in the slides as part of their case-by-case analysis.

This, of course, assumes that you are given a nice-tree decomposition of width $w$, as finding the treewidth of a graph $G$ is NP-hard.

The following paper - http://www.sciencedirect.com/science/article/pii/S0196677496900498 - shows how to go from a regular decomposition to a nice one, in an efficient manner.

$\endgroup$
  • $\begingroup$ You can also be given a (non-nice) tree decomposition, as it's easy to convert it into a nice tree decomposition. $\endgroup$ – Juho Jun 6 '16 at 19:47
  • $\begingroup$ You are right, I've added that to my answer. $\endgroup$ – user340082710 Jun 6 '16 at 20:02

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.