Editing Tree decomposition (section)

==Dynamic programming==
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'',{{sfnp|Bertelé|Brioschi|1972}} a parameter related to treewidth. Later, several authors independently observed, at the end of the 1980s,<ref>{{harvtxt|Arnborg|Proskurowski|1989}}; {{harvtxt|Bern|Lawler|Wong|1987}}; {{harvtxt|Bodlaender|1988}}.</ref> that many algorithmic problems that are [[NP-completeness|NP-complete]] for arbitrary graphs may be solved efficiently by [[dynamic programming]] for graphs of bounded treewidth, using the tree-decompositions of these graphs.

As an example, consider the problem of finding the [[maximum independent set]] in a graph of treewidth {{mvar|k}}. To solve this problem, first choose one of the nodes of the tree decomposition to be the root, arbitrarily. For a node {{mvar|X{{sub|i}}}} of the tree decomposition, let {{mvar|D{{sub|i}}}} be the union of the sets {{mvar|X{{sub|j}}}} descending from {{mvar|X{{sub|i}}}}. For an independent set <math>S \subset X_i,</math> let {{math|''A''(''S'',''i'')}} denote the size of the largest independent subset {{mvar|I}} of {{mvar|D{{sub|i}}}} such that <math>I \cap X_i = S.</math> Similarly, for an adjacent pair of nodes {{mvar|X{{sub|i}}}} and {{mvar|X{{sub|j}}}}, with {{mvar|X{{sub|i}}}} farther from the root of the tree than {{mvar|X{{sub|j}}}}, and an independent set <math>S \subset X_i \cap X_j,</math> let {{math|''B''(''S'',''i'',''j'')}} denote the size of the largest independent subset {{mvar|I}} of {{mvar|D{{sub|i}}}} such that <math>I \cap X_i  \cap X_j = S.</math> We may calculate these {{mvar|A}} and {{mvar|B}} values by a bottom-up traversal of the tree:
:<math>A(S,i)=|S| + \sum_{j} \left(B(S\cap X_j, j,i) - |S\cap X_j|\right)</math>
:<math>B(S,i,j)=\max_{S'\subset X_i\atop S=S'\cap X_j} A(S',i)</math>
where the sum in the calculation of <math>A(S,i)</math> is over the children of node {{mvar|X{{sub|i}}}}.

At each node or edge, there are at most {{math|2{{sup|''k''}}}} sets {{mvar|S}} for which we need to calculate these values, so if {{mvar|k}} is a constant then the whole calculation takes constant time per edge or node. 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. Similar algorithms apply to many other graph problems.

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 [[approximation algorithm|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.<ref name="b96"/>