# Tree decomposition - Fastest algorithm in practise

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?

• 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... – vzn Apr 21 '15 at 21:57

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.
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.