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, a parameter related to treewidth. Later, several authors independently observed at the end of the 1980s that many algorithmic problems that are 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 Xi of the tree decomposition, let Di be the union of the sets Xj descending from Xi. For an independent set S ⊂ Xi, let A(S,i) denote the size of the largest independent subset I of Di such that I ∩ Xi = S. Similarly, for an adjacent pair of nodes Xi and Xj, with Xi farther from the root of the tree than Xj, and an independent set S ⊂ Xi ∩ Xj, let B(S,i,j) denote the size of the largest independent subset I of Di such that I ∩ Xi ∩ Xj = S. We may calculate these A and B values by a bottom-up traversal of the tree:
where the sum in the calculation of is over the children of node .
At each node or edge, there are at most 2k sets S for which we need to calculate these values, so if 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 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.
Read more about this topic: Tree Decomposition
Famous quotes containing the words dynamic and/or programming:
“We Americans have the chance to become someday a nation in which all radical stocks and classes can exist in their own selfhoods, but meet on a basis of respect and equality and live together, socially, economically, and politically. We can become a dynamic equilibrium, a harmony of many different elements, in which the whole will be greater than all its parts and greater than any society the world has seen before. It can still happen.”
—Shirley Chisholm (b. 1924)
“If there is a price to pay for the privilege of spending the early years of child rearing in the driver’s seat, it is our reluctance, our inability, to tolerate being demoted to the backseat. Spurred by our success in programming our children during the preschool years, we may find it difficult to forgo in later states the level of control that once afforded us so much satisfaction.”
—Melinda M. Marshall (20th century)