# Program for computing Tree decomposition of a graph

Does anybody know of an open-source program for computing Tree decomposition of graphs for a fixed "k"(width)? I know that the problem of finding Tree-Decomposition is NP-Hard for variable "k", but my input instances will be really small (~10 nodes) and "k" is fixed.

## 5 Answers

Some of these software might help you. (Not all of them are open-source though.)

*dlib http://dlib.net/

• I don't see the relevance of dlib; the Bayesian network join tree algorithm is related to treewidth but this implementation doesn't seem to help with computing a tree decomposition. Radu Marinescu's treeDecomp might also be useful: graphmod.ics.uci.edu/group/treeDecomp Apr 13, 2011 at 8:51
• The create join tree function in dlib takes a graph and returns its tree decomposition. Apr 13, 2011 at 19:51
• @Davis: Thanks for the explicit pointer, missed that in the documentation. Apr 14, 2011 at 20:06
• The link to LibTW redirects to the author's (Dutch) consulting firm. Is there a new URL? Jun 29, 2018 at 18:59

If $n \sim 10$ and $k$ is fixed, then you can even afford to go with an XP algorithm like the one we implemented for our Android app. The source code is here: TreewidthInspector, and for instance with $n \leq 13$ and $k \leq 4$ it terminates in less than a second.

It's approximately 170 lines of code and it's GPL (or MIT or BSD or whatever you should need).

For $n\le150$ you can use the webservice over at http://treedecompositions.com/ to directly obtain and visualize a quick and reasonable decomposition, without having to compile or install anything.

LibTW can still be found. It's at http://www.treewidth.com/treewidth/ .

You may also be interested in the more modern algorithms FlowCutter (GitHub) and the algorithms by Tamaki et al. (GitHub)