# Dynamic programming and shortest path problem

Several months back, I asked in math.SE the following question

I wonder if any dynamic programming problem can always be converted to a source-sink shortest path problem in a network with source and sink nodes given?

The reason I asked is because I always pictured the type of problems that could be solved by dynamic programming method as source-sink shortest path problems. In other words, the type of problems seemed to always have the interpretation as source-sink shortest path problems, but I was not sure if it was correct.

The only answer I have got so far is

The answer is no. The simplest example off the top of my head is the longest substring of ones in a 0,1 string. The typical DP solution would be to use a 1D array and store the length of the longest substring up that includes the i-th character in the i-th coordinate.

why is the example not able to be formulated into a source-sink shortest path problem in a network?

I don't really see an easy way of doing it as a source-sink SPP. For the DP solution, the answer is obtained by scanning the array for the largest number.

I am now still not sure how DP solves the longest substring of ones in a 0,1 string, and whether this problem can be interpreted as a source-sink shortest path problem. Also I feel the answerer may run out of idea from his reply. Since my question may also be relevant to algorithm theory, I hope there will be some reply from this site.

Thanks and regards!

• A possibly on-topic question would be, "Does every problem that admits optimal substructure have graph-theoretic characterization X?" Sep 6, 2011 at 16:35
• Sasho asked for an example. You ignored this. Tsuyoshi pointed out you didn't define the problem. You said you did even though the page you linked to clearly doesn't (which was why your response seemed rude to me). I've already suggested two questions you could ask. You have ignored this too. Could you please write down what "dynamic programming problem" means and give a concrete example? Or don't. Sep 6, 2011 at 17:04
• @Tim, the wikipedia article does not define dynamic programming mathematically, it is an intuitive concept but to prove results you need to give a mathematical definition for what is a DP algorithm, see for example "Toward a Model for Backtracking and Dynamic Programming" by Alekhnovich, Borodin, Buresh-Oppenheim, Impagliazzo, Magen, and Pitassi from CCC 2005. (also note that they call it a model for DP, not the model for DP, "what is the right model for DP?" is an active research area). Sep 6, 2011 at 17:35
• I think we should err on others acting nicely than erring in the other direction, written medium is not as expressive as face to face discussions. :) I guess that Tim didn't notice that Wikipedia article is not giving a mathematical definition of DP that can be used for answering his question. It would be nice if at some point someone adds a section to the Wikipedia article about proposed mathematical models for DP algorithms. Sep 6, 2011 at 19:42
• I think everyone needs to take a break here :). @Tim, I think Chandra has probably the clearest answer you're going to get, mainly because the notion of "what is dynamic programming" is not completely well defined. Sep 6, 2011 at 22:04

One standard view of dynamic programming is the following. Start with a recursive algorithm and then memoize it. By memoization we mean that solutions for intermediate problem instances/sub-problems are stored and not recomputed. If one can argue that the number of sub problems generated in the recursive algorithm for an instance of size $n$ is polynomial in $n$ then memoization leads to a polynomial time algorithm. A recursive algorithm for a problem instance $I$ generates, naturally, an associated DAG $G(I)$ whose nodes are the sub-problem instances and the arcs are the dependencies generated by the recursive algorithm on $I$. It is possible to interpret several different computational problems as solving some kind of shortest path problem on this DAG $G(I)$ (not all though). In these cases it is possible to take out the scaffolding of the recursive algorithm and memoization and directly use a shortest path algorithm in an associated graph. This should not lead one to conclude that all of dynamic programming can be reduced to shortest path computation.

Shortest paths in DAGs are typically problems in NL and many times complete as well. A slightly "larger" class is LOGCFL (of course, we don't know if NL=?LOGCFL) where typical problems solvable with dynamic programming live. (Typical here means polynomial time. Unlike for example, DPs for knapsack type problems that take exponential time.)

As an example, consider the word problem on groupoids. You have a groupoid table and a word $a_1 ... a_n$ and the question is whether we can bracket the word in some way so that it evaluates to identity. (Note that the groupoid table need not be associative.) This problem is complete for LOGCFL. Here is a reference; if I remember correctly, this goes back to Valiant.

So it would seem that typical DPs are more powerful than typical shortest path problems under typical complexity theoretic assumptions! Given the vagueness of what constitutes DP, this is as far as we can say.

update: Suresh, here is one way to see. LOGCFL is a nondeterministic machine (like NP) but running in log space, polynomial time, with a stack. Think of the final solution as a witness. It will be a polynomial sized proof tree (because I assumed polynomial running time) with the children being the "smaller" subproblems etc. But to traverse this tree, you will have to explore all children at a node and therefore you need a stack. (Because of the logspace restriction, you don't have space to record the witness and then check).

• That's very interesting. I was not aware that LOGCFL was the natural class for many DPs. Is there any easy way to see this ? Sep 7, 2011 at 4:45
• What's a groupoid? The definition I know is that it's a category in which all morphisms have inverses, but somehow I don't think that's what you have in mind.... Sep 7, 2011 at 12:45
• @Neel: When you decategorify the category-theoretic definition, you get the algebraic definition of groupoid. I assume what is being discussed here is a finite algebraic groupoid presented by a multiplication table. Sep 7, 2011 at 19:23
• I think all so-called "incremental" DP algorithms (including that for the max contiguous 1-subsequence problem and many others) CAN be implemented as instances of "lightest" or "heaviest" s-t path problems. In an incremental" algorithm, the sums are restricted to the form: value of a subproblem plus the cost of a data item queried at that wire. I have a draft paper on this (things are in embryos stage, however). Nov 8, 2011 at 10:32

Here's a less formal answer that I hope nonetheless addresses the spirit of the question.

Many standard dynamic-programming algorithms are easily seen to be equivalent to shortest-path (or longest-path) in the DAG of subproblems (per Chandra's answer). But some common ones that don't fit this pattern include minimum-weight triangulation of a polygon, and finding optimal binary search trees.

To explain, consider the standard dynamic program for minimum-weight polygon triangulation. Fix an input instance $$p[1..n]$$, where $$p[i]$$ is the $$i$$th point (in $$\mathbb R^2$$). For each pair $$(i, j)$$ with $$1\le i < j \le n$$ and $$j-i\ge 1$$, define $$T(i, j)$$ to be the optimal cost for the subproblem $$p[i..j]$$ formed by the $$j-i+2$$ points $$p[i], p[i+1], \ldots, p[j]$$. The final answer is $$T(1, n)$$. The recurrence relation is

$$\mathbf{T(i, j)} = \begin{cases} d(p[i], p[j]) & (j=i+1) \\ \min \big\{ \mathbf{T(i, k) + T(k, j)} + d(p[i],p[j]) : k \in \{i+1,\ldots, j-1\}\big\} & (j > i+1). \end{cases}$$

If we consider the underlying DAG, the recurrence is not easily modeled as a shortest- or longest-path problem on that DAG, because, although the cost associated with the node for the subproblem $$T(i, j)$$ is expressed as a minimum of terms (as it would be in a shortest-path problem), each term involves the sum of two subproblems, $$T(i, k) + T(k, j)$$. As far as I know, because of this there is no natural re-interpretation as a shortest-path problem.

I think the combinatorial problem that more naturally underlies this dynamic program is finding a minimum-cost binary search tree in the underlying DAG, as is made explicit in the dynamic program for computing optimal binary search trees, which resembles this one very closely.