Tree decomposition: Difference between revisions

Revision as of 02:04, 21 February 2013

Revision as of 05:07, 21 February 2013

Line 30:

==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'',<ref>{{harvtxtsfnp|Bertelé|Brioschi|1972}}</ref> 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_i'' of the tree decomposition, let ''D_i'' be the union of the sets ''X_j'' descending from ''X_i''. For an independent set ''S''&nbsp;⊂&nbsp;''X_i'', let ''A''(''S'',''i'') denote the size of the largest independent subset ''I'' of ''D_i'' such that ''I''&nbsp;∩&nbsp;''X_i''&nbsp;=&nbsp;''S''. Similarly, for an adjacent pair of nodes ''X_i'' and ''X_j'', with ''X_i'' farther from the root of the tree than ''X_j'', and an independent set ''S''&nbsp;⊂&nbsp;''X_i''&nbsp;∩&nbsp;''X_j'', let ''B''(''S'',''i'',''j'') denote the size of the largest independent subset ''I'' of ''D_i'' such that ''I''&nbsp;∩&nbsp;''X_i''&nbsp;∩&nbsp;''X_j''&nbsp;=&nbsp;''S''. We may calculate these ''A'' and ''B'' values by a bottom-up traversal of the tree:

Line 70:

| journal = Journal of Algorithms

| volume = 8 | issue = 2 | year = 1987 | pages = 216–235 | doi = 10.1016/0196-6774(87)90039-3}}.

*{{citation

| last1 = Bertelé | first1 = Umberto

| last2 = Brioschi | first2 = Francesco

| title = Nonserial Dynamic Programming

| year = 1972

| publisher = Academic Press

| isbn = 0-12-093450-7}}.

*{{citation

| last = Bodlaender | first = Hans L. | authorlink = Hans L. Bodlaender