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!
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
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.
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.
Do your graphs have some special features? The ISGCI 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.)
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 Perl implementation of an older algorithm, Nathann Cohen is currently working to incorporate a more recent C implementation into the Sage framework, or you could use Fabien de Montgolfier's C code directly if you read French (the papers describing the work are in English).
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.
answered Jul 1, 2010 at 20:39
$\begingroup$
$\endgroup$
Some tree decomposition software is given here: http://hein.roehrig.name/dipl/. I haven't used it so can say nothing about it's quality.
$\begingroup$
$\endgroup$
0
You could try the LibTW software, which is freely available from http://www.treewidth.com/ (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.
