15-1 Longest simple path in a directed acyclic graph

Suppose that we are given a directed acyclic graph $G = (V, E)$ with real-valued edge weights and two distinguished vertices $s$ and $t$ . Describe a dynamic-programming approach for finding a longest weighted simple path from $s$ to $t$. What does the subproblem graph look like? What is the efficiency of your algorithm?

First, we clarify the question. We define the weight of a path to be the sum of the weights of the edges in the path. Then, our task is to find the path from $s$ to $t$ that has the largest weight.

$\textbf{Dynamic-programming approach}$

From a given vertex, we try all outgoing edges and take the max over the weights of the resulting paths. That is, for some vertex $v$, $$ \text{LONGEST}(G, v, t) = \max_{v∼v'} w((v, v’)) + \text{LONGEST}(G, v’, t) $$ where $w: E \rightarrow \mathbb{R}$ is a function mapping edges to their weights. The natural base case is that $\text{LONGEST}(G, t, t) = 0$. Applying this recurrence relation along with memoization gives a dynamic programming solution.

$\textbf{Subproblem graph}$

The subproblem graph is simply the subgraph of our original graph that consists of vertices and edges that lie on some path from $s$ to $t$. This is because the initial problem asks for the longest weighted path from $s$ to $t$, and then this request asks for the longest weighted path from each of $s$’s neighbors to $t$, and so on.

$\textbf{Algorithm efficiency}$

In the worst case (for example, consider a graph that "starts with $s$ and ends with $t$", meaning that every vertex lies on a path from $s$ to $t$), we have $|V|$ distinct subproblems. In this case, we also explore all edges (we explore the edge $(v,w)$ in the subproblem $\text{LONGEST}(G, v, t)$). So, our time complexity is $O(|V| + |E|)$.

$\textbf{Verifying overlapping subproblems and optimal substructure}$

In order to use DP, we must verify that (a) there are overlapping subproblems and (b) we have optimal substructure.

For (a), consider a graph that has the following subgraph: ${(a, b), (a, c), (b, d), (c, d)}$ (imagine that $s$ has an edge to $a$ and $d$ has an edge to $t$). Then, we will ask for the solution to $\text{LONGEST}(G,d,t)$ twice (once from $b$ and once from $c$).

For (b), suppose we have the longest weight simple path from $s$ to $t$. Let $v$ be the first vertex after $s$ in our path. Suppose $v \rightsquigarrow t$ is not the longest weight simple path from $v$ to $t$. Then, there is a longer simple path $v \rightsquigarrow t$. If it included $s$, then we have a path $s \rightsquigarrow v$ and a path $v \rightsquigarrow s$, so our graph is not acyclic. Thus, this longer path does not include $s$. So, we can construct a longer weight simple path from $s$ to $t$ than our original path by going from $s$ to $v$ and then taking the longer weight path from $v$ to $t$. We conclude that our original path was not the longest weight simple path from $s$ to $t$, contradiction.