Tree decomposition
They play an important role in problems like probabilistic inference, constraint satisfaction, query optimization,[1] and matrix decomposition.
The concept of tree decomposition was originally introduced by Rudolf Halin (1976).
Later it was rediscovered by Neil Robertson and Paul Seymour (1984) and has since been studied by many other authors.
Each subtree associates a graph vertex with a set of tree nodes.
To define this formally, we represent each tree node as the set of vertices associated with it.
[4] The width of a tree decomposition is the size of its largest set Xi minus one.
The treewidth tw(G) of a graph G is the minimum width among all possible tree decompositions of G. In this definition, the size of the largest set is diminished by one in order to make the treewidth of a tree equal to one.
Treewidth may also be defined from other structures than tree decompositions, including chordal graphs, brambles, and havens.
It is NP-complete to determine whether a given graph G has treewidth at most a given variable k.[5] However, when k is any fixed constant, the graphs with treewidth k can be recognized, and a width k tree decomposition constructed for them, in linear time.
At the beginning of the 1970s, it was observed that a large class of combinatorial optimization problems defined on graphs could be efficiently solved by non-serial dynamic programming as long as the graph had a bounded dimension,[6] a parameter related to treewidth.
As an example, consider the problem of finding the maximum independent set in a graph of treewidth k. To solve this problem, first choose one of the nodes of the tree decomposition to be the root, arbitrarily.
The size of the maximum independent set is the largest value stored at the root node, and the maximum independent set itself can be found (as is standard in dynamic programming algorithms) by backtracking through these stored values starting from this largest value.
Thus, in graphs of bounded treewidth, the maximum independent set problem may be solved in linear time.
This dynamic programming approach is used in machine learning via the junction tree algorithm for belief propagation in graphs of bounded treewidth.
It also plays a key role in algorithms for computing the treewidth and constructing tree decompositions: typically, such algorithms have a first step that approximates the treewidth, constructing a tree decomposition with this approximate width, and then a second step that performs dynamic programming in the approximate tree decomposition to compute the exact value of the treewidth.
