7
$\begingroup$

I'm looking for a fast in practice algorithm for calculating the (preferable optimized) tree decomposition of a graph.

I found the paper "A linear time algorithm for finding tree-decompositions of small treewidth" [1] by Hans L. Bodlaender which return a tree-decompsiton with the optimized tree-width and as the name says, the algorithm runs in linear time but since there are no (translation: I have not found ) any implementations, I am not sure if it's being used in practice or not.

Is the paper by Hans L. used in practice or does the constant factor make the algorithm useless?

[1] http://dl.acm.org/citation.cfm?id=167161

[2] http://www.treewidth.com/docs/libtw.pdf

Edit: Linked https://math.stackexchange.com/questions/1246421/tree-decomposition-by-hand-for-understanding

$\endgroup$
1
  • 1
    $\begingroup$ take a look at a rare question that slipped by cstheory.se, open source pkgs for tree decomposition & you can see what algorithms these pkgs used, & validate instances, etc... there are also good Q/As on tree decomposition there. good luck with this, hope you succeed, the algorithm is not very simple to implement/ test, & would like to hear more/ status updates in Computer Science Chat... $\endgroup$
    – vzn
    Apr 21, 2015 at 21:57

1 Answer 1

11
$\begingroup$

The first caveat is that deciding whether the treewidth of a graph is at most $t$ is NP-complete, but it is FPT (which is what Bodlaender's paper shows). So for small $t$, we can (in principle) solve the problem exactly (and actually spit out the decomposition as well), but for graphs with large treewidth, then things can get a bit slow.

Having said that, you're right, the hidden constants in Bodlaender's algorithm are prohibitive, but there are more practical ways of getting at least a good tree decomposition. A useful place to start is with another of Bodlaender's papers, "A tourist guide to treewidth", which is now a bit old, but still has some valuable information and references to algorithms for generating tree decompositions, particularly in various restricted graph classes (sometimes the algorithms work in general, you just don't get a nice upper bound on the running time outside of the restricted class). John Fouhy's master's thesis "Computational experiments on graph width metrics" includes a number of way of obtaining tree decompositions (you can find it here under the link "John's thesis").

Probably most useful though is if you can get a copy of Downey and Fellow's new book "Fundamentals of Parameterized Complexity" (Springer, 2013), in which they devote Chapter 11 to heuristics for finding tree decompositions. This is probably the most recent survey in covering this material. They also note that the handful of attempts at implementing Bodlaender's algorithm have not been successful because it was impractically slow, so your lack of success in finding implementations is no coincidence. Bodlaender's algorithm works via recursive application of an FPT algorithm, the problem being that the recursion depth depends on the treewidth, (checking Downey & Fellows, the recursive depth is $O(t^8)$) which just becomes too prohibitively slow too quickly.

$\endgroup$
6
  • $\begingroup$ Do you now were I can find an implementation online in C++ were the graph structure is a linked representation? $\endgroup$
    – Bojack
    Apr 21, 2015 at 14:54
  • $\begingroup$ @NiclasJonsson Which version are you implementing? We implemented an XP algorithm quite easily for an Android app. The source code is here: TreewidthInspector $\endgroup$
    – Pål GD
    Apr 21, 2015 at 15:33
  • $\begingroup$ I am using C++11. Does it just calculate the tree width or does it return the tree composition as well? $\endgroup$
    – Bojack
    Apr 21, 2015 at 15:41
  • $\begingroup$ @NiclasJonsson It currently only computes the treewidth, because we didn't know how we wanted to display the tree decomposition. But it's a simple fix to also get the bags. $\endgroup$
    – Pål GD
    Apr 22, 2015 at 1:46
  • $\begingroup$ @NiclasJonsson Requests for source code are offtopic here. $\endgroup$
    – Raphael
    Apr 22, 2015 at 7:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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