Content deleted Content added
Line 34:
==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 ''k''. To solve this problem, first choose one of the nodes of the tree decomposition to be the root, arbitrarily. For a node ''X<sub>i</sub>'' of the tree decomposition, let ''D<sub>i</sub>'' be the union of the sets ''X<sub>j</sub>'' descending from ''X<sub>i</sub>''. For an independent set ''S'' ⊂ ''X<sub>i</sub>'', let ''A''(''S'',''i'') denote the size of the largest independent subset ''I'' of ''D<sub>i</sub>'' such that ''I'' ∩ ''X<sub>i</sub>'' = ''S''. Similarly, for an adjacent pair of nodes ''X<sub>i</sub>'' and ''X<sub>j</sub>'', with ''X<sub>i</sub>'' farther from the root of the tree than ''X<sub>j</sub>'', and an independent set ''S'' ⊂ ''X<sub>i</sub>'' ∩ ''X<sub>j</sub>'', let ''B''(''S'',''i'',''j'') denote the size of the largest independent subset ''I'' of ''D<sub>i</sub>'' such that ''I'' ∩ ''X<sub>i</sub>'' ∩ ''X<sub>j</sub>'' = ''S''. We may calculate these ''A'' and ''B'' values by a bottom-up traversal of the tree:
| |||