Program for computing Tree decomposition of a graph

Question

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.

Meta discussion: http://meta.cstheory.stackexchange.com/questions/1101/questions-about-finding-code-for-algorithms. Please visit the meta site before posting any answers - I'm questioning whether this question is in scope or not. — Suresh Venkat, Apr 13 '11 at 04:59

score 22 · Answer 1 · edited Sep 25 '18 at 11:31

22

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/

edited Sep 25 '18 at 11:31

Gamow

5,772
6
25
39

answered Apr 13 '11 at 04:45

Snowie

1,200
7
10

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: http://graphmod.ics.uci.edu/group/treeDecomp – András Salamon Apr 13 '11 at 08:51
3

The create join tree function in dlib takes a graph and returns its tree decomposition. – Davis King Apr 13 '11 at 19:51
@Davis: Thanks for the explicit pointer, missed that in the documentation. – András Salamon Apr 14 '11 at 20:06
1

The link to LibTW redirects to the author's (Dutch) consulting firm. Is there a new URL? – Jeffε Jun 29 '18 at 18:59

score 7 · Answer 2 · answered Apr 22 '15 at 01:51

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

score 5 · Answer 3 · answered Nov 06 '16 at 19:34

5

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.

answered Nov 06 '16 at 19:34

Fasermaler

265
2
5

score 5 · Answer 4 · answered Sep 24 '18 at 09:24

5

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

answered Sep 24 '18 at 09:24

Mathijs

161
1
1

score 2 · Answer 5 · answered Sep 24 '18 at 22:39

2

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

answered Sep 24 '18 at 22:39

delete000

818
8
16

Program for computing Tree decomposition of a graph

5 Answers5