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.
1$\begingroup$ Meta discussion: meta.cstheory.stackexchange.com/questions/1101/…. Please visit the meta site before posting any answers - I'm questioning whether this question is in scope or not. $\endgroup$– Suresh VenkatApr 13, 2011 at 4:59
Some of these software might help you. (Not all of them are open-source though.)
$\begingroup$ 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 $\endgroup$ Apr 13, 2011 at 8:51
3$\begingroup$ The create join tree function in dlib takes a graph and returns its tree decomposition. $\endgroup$ Apr 13, 2011 at 19:51
$\begingroup$ @Davis: Thanks for the explicit pointer, missed that in the documentation. $\endgroup$ Apr 14, 2011 at 20:06
1$\begingroup$ The link to LibTW redirects to the author's (Dutch) consulting firm. Is there a new URL? $\endgroup$– Jeffε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)