22
$\begingroup$

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.

$\endgroup$
22
$\begingroup$

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

*LibTW http://www.treewidth.com/treewidth/

$\endgroup$
  • $\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$ – András Salamon Apr 13 '11 at 8:51
  • 3
    $\begingroup$ The create join tree function in dlib takes a graph and returns its tree decomposition. $\endgroup$ – Davis King Apr 13 '11 at 19:51
  • $\begingroup$ @Davis: Thanks for the explicit pointer, missed that in the documentation. $\endgroup$ – András Salamon Apr 14 '11 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 '18 at 18:59
7
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy