Diplomarbeit (Master's Thesis) of Hein Röhrig
My project was to investigate the practicability of general algorithms for computing tree decompositions. The thesis was supervised by Torben Hagerup at the Max-Planck-Institut für Informatik.
Informally, a tree decomposition of a graph is a family of small subgraphs that fit together in a tree-like way to make up the whole graph. The width of a such a decomposition is the maximal size of a subgraph and the treewidth of the graph is the minimal width of any tree decomposition of the graph. The treewidth measures how closely a graph resembles to a tree. The motivation for computing tree decompositions is that many NP-hard graph problems (such as INDEPENDENT SET and 3-COLORING) can be solved in linear time on families of graphs of bounded treewidth, if the input consists of the graph and a tree decomposition.
The problem of deciding whether given a graph and number k, the graph has at most treewidth k is NP-complete. Therefore computing tree decompositions of bounded treewidth (or deciding that the graph has greater treewidth) is NP-hard. However, if we fix k, there exist polynomial time algorithms for deciding tree width and computing tree decompositions. This important theoretical result does not yield practical algorithms in any obvious way, mostly due to very large constants.
The most recent and best theoretical results concerning tree decomposition are due to Hans Bodlaender. As an introduction to treewidth and tree decomposition, I recommend his papers Treewidth: Algorithmic Techniques and Results and A Tourist Guide through Treewidth.