Can dynamic programming problems always be represented as DAG

Question

I am trying to draw a DAG for Longest Increasing Subsequence {3,2,6,4,5,1} but cannot break this into a DAG structure.

Is it possible to represent this in a tree like structure?

Answer 1

As far as I know, the answer to the actual question in the title is, "No, not all DP programs can be reduced to DAGs."

Reducing a DP to a DAG is one of my favorite tricks, and when it works, it often gives me key insights into the problem, so I find it always worth trying. But I have encountered some that seem to require at least hypergraphs, and this paper and related research seems to bear that out.

This might be an appropriate question for the CS Stack Exchange, meaning the abstract question about graph reduction, not the specific question about longest increasing subsequence.

Answer 2

Assuming following Sequence, S = {3,2,6,4,5,1,7,8} and R = root node. Your tree or DAG will look like

              R
      3    2     4    1
           6     5    7
                      8

And your result is the longest path (from root to the node with the maximum depth) in the tree (result = {r,1,7,8}).

The result above show the longest increasing sequence in S. The Tree for the longest increasing subsequence in S look as follows

              R
   3   2   6   4   5   1   7   8
   6   4   7   5   7   7   8  
   7   5   8   7   8   8      
   8   7       8   
       8

And again the result is the longest path (from root to the node with the maximum depth) in the tree (result = {r,2,4,5,7,8}).