I think of dynamic programming as a bottom-up computation, but that view can be slightly misleading. For example, consider keeping track of the connected components of a forest F in a graph of bounded treewidth.
For a bag B, let G(subtree(B)) denote the subgraph induced by the nodes appearing in bag B (let's call those portal nodes) and in all of its descendant bags as well. Let G(B) denote the constant size graph induced by just the portals.
Consider the connected components of (F intersect G(subtree(B))). They induce a partition pi(B) of the portals.
- for a leaf bag, pi(B) = the connected components of (F intersect G(B))
- for a bag B with two children B1 and B2, pi(B) is obtained by "combining" pi(B1), pi(B2), and (F intersect G(B)).
It's a bottom-up recurrence.
Consider instead the connected component of F, the global forest. They also induce a partition sigma(B) of the portals.
- for the root bag, sigma(B)=pi(B)
- for a bag B with parent bag B', sigma(B) is obtained by "combining" sigma(B'), pi(B), and (F intersect G(B union B')).
It's a top-down recurrence.
Since all recurrence formulas are local, a dynamic program can do both computations at the same time, and thus a DP algorithm can be assumed, while it is working on a bag B, to have access to the partition of the portals in the global forest: working bottom up, it makes guesses that will be validated later at a higher level of the tree. Thus, one recurrence is of the form: compute, then memorize a summary of the computation done in G(subtree(B)). The other recurrence is of the form: guess a summary of the future computation, then verify. In the DP the two computations are intertwined.
Borradaile, Klein and myself are using something much like this in a paper on Euclidean Steiner forest. Bateni, Hajiaghayi and Marx are using essentially this in a paper on Steiner forest in planar graphs and graphs of bounded treewidth. Writing up the details of such dynamic programs is a bit messy, yet it is conceptually simple. I think that the difficulty in presentation comes from this mix of bottom-up and top-down.
Are there other examples of such dynamic programs? Are there models of good writing for that?
Well, this is maybe not a very helpful answer, but the exposition in this post seems pretty clear. It sacrifices showing the intertwining, though, I guess.
ReplyDeleteAn example of a dynamic programs where you use information from both bottom and parent as you move in the tree (but it is not exactly the same) is the solution to this A way of looking at a solution, which might be good or not, is that we can just just preprocess the weights below each node in the tree (with an arbitrary root) using DFS, and after that another DFS that manipulates the previously computed values will do the rest. But this requires two steps, so it might not be what you are looking for. Hope it is helpful, anyway.