Essentially, tree decomposition asks for a way to take a set of small sets of vertices and connect them in a way so that vertices shared by any pair of connected sets is a separator of the graph.

Two examples below show a graph on the left and it's optimal tree decomposition on the right

Following problems become easy once you have a good tree decomposition of a graph. Finding best: clique, independent set, dominating set, TSP tour, Steiner Tree. Almost every graph polynomial is tractable to compute given good tree decomposition. Finding BEST tree decomposition is NP-hard, but finding good decomposition is much easier. It parallelizes well, and simple heuristics give decompositions close to optimal for moderate size graphs even on my two-processor laptop.

Here are two relevant notebooks:

Wow I am fond of your tree-decomposition program !!!!!!!!!! Thank you for sharing it, this is the true spirit of sciences !

ReplyDeleteYou can get the latest version of the packages there from the link in my last blog post http://mathematica-bits.blogspot.com/2011/03/graph-utilities-i-use.html

ReplyDeleteThis comment has been removed by the author.

ReplyDelete