Dynamic programming and shortest path problem

Question

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.

When I further asked:

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

The reply is:

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!

Answer 1

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.

Answer 2

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).

Answer 3

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.