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.
$\begingroup$
$\endgroup$
1
-
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 VenkatCommented Apr 13, 2011 at 4:59
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
4
Some of these software might help you. (Not all of them are open-source though.)
*TreeD http://www.itu.dk/people/sathi/treed/
*dlib http://dlib.net/
*QuickBB http://www.cs.washington.edu/homes/vgogate/quickbb.html
*Hypertree http://www.dbai.tuwien.ac.at/proj/hypertree/downloads.html
-
$\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$ Commented Apr 13, 2011 at 8:51
-
3$\begingroup$ The create join tree function in dlib takes a graph and returns its tree decomposition. $\endgroup$ Commented Apr 13, 2011 at 19:51
-
$\begingroup$ @Davis: Thanks for the explicit pointer, missed that in the documentation. $\endgroup$ Commented 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εCommented Jun 29, 2018 at 18:59
$\begingroup$
$\endgroup$
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).
$\begingroup$
$\endgroup$
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.
