most recent 30 from http://mathoverflow.net 2013-05-20T09:07:16Z http://mathoverflow.net/feeds/question/30191 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/30191/software-for-tree-decompositions simone 2010-07-01T14:39:34Z 2010-07-12T13:12:40Z

<p>Does anybody know about software that exactly calculates the tree-width of a given graph and outputs a tree-decomposition? I am only interested in tree-decompositions of reasonbly small graphs, but need the exact solution and a tree-decomposition. Any comments would be great. Thanks!</p>

http://mathoverflow.net/questions/30191/software-for-tree-decompositions/30193#30193 supercooldave 2010-07-01T14:44:32Z 2010-07-01T14:44:32Z

<p>Some tree decomposition software is given here: <a href="http://hein.roehrig.name/dipl/" rel="nofollow">http://hein.roehrig.name/dipl/</a>. I haven't used it so can say nothing about it's quality.</p>

http://mathoverflow.net/questions/30191/software-for-tree-decompositions/30230#30230 András Salamon 2010-07-01T20:39:28Z 2010-07-01T20:39:28Z

<p>For general graphs there are no good algorithms known, as the problem of determining the treewidth of a graph is NP-hard. So if your graphs are not from some special class, and instances are small, then a brute force search over all decompositions of small width is a reasonable approach.</p> <p>As a previous answer suggested, Röhrig's Diplomarbeit ranks highly in a Google search. His rather negative conclusion in 1998 was that when treewidth exceeds $4$, brute force enumeration was essentially the only realistic option; up to $4$ special-purpose algorithms were reasonable. This is not that surprising, as (intuitively speaking) iterating over all choices of bags of up to $k$ elements takes $\Omega(n^k)$ time, so the runtime grows quite fast.</p> <p>Do your graphs have some special features? The <a href="http://wwwteo.informatik.uni-rostock.de/isgci/" rel="nofollow">ISGCI</a> has many special graph classes, for some of which it is possible to find join-trees efficiently. (Join-tree decompositions are another name for tree decompositions, although this term nowadays seems to usually refer to join trees as used in Bayesian networks.)</p> <p>Taking a really high level perspective, do you really want to compute tree decompositions? If you are decomposing trees because you need to do something with them, then consider an easier-to-compute decomposition. For instance, the modular decomposition can be computed in linear time, and also guarantees fast algorithms for many problems via the modular decomposition tree. There is a <a href="http://search.cpan.org/~azs/Graph-ModularDecomposition/" rel="nofollow">Perl implementation</a> of an older algorithm, <a href="http://www-sop.inria.fr/members/Nathann.Cohen/tut/Graphs/" rel="nofollow">Nathann Cohen</a> is currently working to incorporate a more recent C implementation into the <a href="http://www.sagemath.org/" rel="nofollow">Sage</a> framework, or you could use <a href="http://www.liafa.jussieu.fr/~fm/algos/index.html" rel="nofollow">Fabien de Montgolfier's C code</a> directly if you read French (the papers describing the work are in English).</p> <p>If you really do need tree decompositions, then have a look at the simple approach via induced width, which can be easily implemented (and parallelized) by considering each possible vertex ordering, then checking the induced width it corresponds to. Section 2.3 of Rina Dechter's draft version of her chapter from the Handbook of Constraint Programming is quite useful as a starting point.</p>

http://mathoverflow.net/questions/30191/software-for-tree-decompositions/31545#31545 Bart Jansen 2010-07-12T13:12:40Z 2010-07-12T13:12:40Z

<p>You could try the LibTW software, which is freely available from <a href="http://www.treewidth.com/" rel="nofollow">http://www.treewidth.com/</a> (also read their FAQ linked at the bottom of the page). It's written in Java so you can easily extend it with your own functionality.</p>