Skip to main content

DP on DAGs and Graph-Based DP

What This Concept Is​

Every correct DP induces a directed acyclic graph (DAG) of subproblems: nodes are subproblem states, edges go from a subproblem to each subproblem it depends on, and the graph is acyclic because each subproblem is strictly smaller in some well-founded order. Filling the DP table in a valid order is equivalent to doing a topological traversal of this DAG.

Making the DAG explicit lets you:

  • Solve longest path in a DAG in linear time: process vertices in topological order; $dp[v] = \max_{(u,v) \in E}(dp[u] + w(u,v))$.
  • Solve number of paths from $s$ to $t$ in a DAG via the same topological sweep with +.
  • Recognize that many DP problems (LIS, edit distance, shortest monotonic paths, scheduling with precedence) are literally longest/shortest paths on implicit DAGs.
  • Handle problems with precedence constraints naturally -- topological order is built into the DP.

In the reverse direction, when a DP state is hard to see, reformulating the problem as "find an optimal path on this DAG" sometimes reveals it. This is Erik Demaine's SRTBOT framing in MIT 6.006: every DP = Subproblems + Relate + Topological order + Base cases + Original problem + Time complexity.

More formally: a DP is well-defined iff its subproblem-dependency graph is a DAG. If it has a cycle, the recurrence is self-referential and the computation never terminates. Bellman-Ford and value iteration are DPs over cyclic graphs that converge via iteration to a fixed point -- a separate structural class.

Why It Matters Here​

Viewing DP as a DAG computation unifies the module. The fill order is topological order; the recurrence is an edge relaxation; reconstruction is a walk of parent pointers. Problems that feel unrelated -- scheduling, LIS, shortest-path-in-a-grid, task-critical-path -- become instances of the same pattern. This unification is the single biggest payoff of finishing the DP module.

Note that longest path in a general graph is NP-hard, because cycles allow infinite extension (with positive edges) or require cycle-avoidance (NP-hard in itself). Longest path in a DAG is polynomial precisely because of acyclicity.

The DAG viewpoint also clarifies when DP is not the right tool: if the problem's natural subproblem graph has cycles and you cannot iterate to a fixed point (either because the costs are not contractive or because there is no such fixed point), you need Dijkstra, Bellman-Ford, BFS, or another graph algorithm.

Concrete Examples​

Example 1: Longest path in a DAG. Given a DAG $G = (V, E)$ with edge weights $w$, compute $dp[v]$ = the length of the longest path ending at $v$.

  1. Topological-sort $V$.
  2. Initialize $dp[v] = 0$ for all $v$ (or $-\infty$ if paths must start at a specific source).
  3. Process vertices in topological order. For each outgoing edge $(v, u)$, update $dp[u] = \max(dp[u], dp[v] + w(v, u))$.
  4. Answer = $\max_v dp[v]$.

Time $O(V + E)$.

Example 2: LIS as longest path on a DAG. Build a DAG on indices $1..n$ where there is an edge $i \to j$ when $i < j$ and $a[i] < a[j]$, each edge of weight 1. Add a source $0$ with $a[0] = -\infty$ and an edge from $0$ to every vertex. The longest path from $0$ is the LIS length + 1. The $O(n^2)$ LIS DP is literally a topological sweep of this DAG.

Example 3: Number of monotonic paths from $(0,0)$ to $(m-1, n-1)$ in a grid. The grid with right/down moves is a DAG; count paths by the same sweep with $+$.

$$dp[v] = \sum_{(u,v) \in E} dp[u], \quad dp[\text{source}] = 1.$$

Example 4: Critical path method (CPM). Given a task graph with durations and dependencies (a DAG), the critical path -- longest path from start to end -- gives the minimum total time to finish all tasks. This is foundational to project management (PERT, Gantt). It is identical to "longest path on a DAG."

Example 5: Bellman-Ford as DP on iterations. On a general graph with $V$ vertices, $dp[k][v]$ = shortest $s \to v$ path using at most $k$ edges. Recurrence:

$$dp[k][v] = \min\big( dp[k-1][v],\ \min_{(u,v) \in E} dp[k-1][u] + w(u,v) \big).$$

The "layer" index $k$ makes the subproblem DAG acyclic even though the original graph has cycles. This is why Bellman-Ford is a DP despite operating on cyclic graphs.

Example 6: Shortest path in a DAG (single source). Topologically sort vertices; process in order; for each vertex $v$ and each outgoing edge $(v, u)$, relax $d[u] = \min(d[u], d[v] + w(v, u))$. $O(V + E)$ time -- strictly faster than Dijkstra on DAGs, and handles negative edge weights that Dijkstra cannot.

Worked trace -- longest path in a 5-vertex DAG. Edges (with weights): $1\to2:3,\ 1\to3:2,\ 2\to4:4,\ 3\to4:1,\ 4\to5:2$. Topological order: $1,2,3,4,5$. Initialize $dp=[0,0,0,0,0]$. Process $1$: $dp[2]=\max(0,0+3)=3$, $dp[3]=\max(0,0+2)=2$. Process $2$: $dp[4]=\max(0,3+4)=7$. Process $3$: $dp[4]=\max(7,2+1)=7$ (unchanged). Process $4$: $dp[5]=\max(0,7+2)=9$. Process $5$: no outgoing. Answer: longest path length $9$, via $1\to2\to4\to5$. The fill is literally for v in topo: for (v,u) in out[v]: dp[u] = max(dp[u], dp[v] + w).

Common Confusion / Misconceptions​

"DP works on any graph." DP-on-DAGs requires acyclicity. On graphs with cycles and nonnegative weights, Dijkstra's algorithm is the correct tool for shortest paths. On graphs with general weights and no negative cycles, Bellman-Ford is. DP-on-DAGs covers a specific, simpler case; do not generalize it beyond DAGs without proof.

"Build the explicit DAG every time." For LIS, you do not materialize $O(n^2)$ edges -- you just loop $j < i$. The DAG view is a mental model for reasoning; the implementation stays compact.

"Topological order is unique." Usually not -- most DAGs have many valid topological orderings. Any one of them suffices for DP. The lexicographically smallest topological order is a specific choice useful for tie-breaks; the DP result is order-independent.

"All DPs fit the DAG framework." Most do. A rare exception: DPs over infinite state spaces (continuous-state MDPs, unbounded integers) need a different framework -- convergence of iterative schemes rather than a finite DAG sweep.

"Longest simple path in a DAG is the same as longest path in a DAG." Yes, because in a DAG all paths are automatically simple (no repeated vertices). This is why DAG longest path is polynomial while general-graph longest simple path is NP-hard.

How To Use It​

  1. Identify the subproblem DAG implicit in a recurrence: nodes are states, edges are dependencies.
  2. Verify acyclicity (every edge decreases some measure -- index, interval length, subset size, layer).
  3. Fill the DP in topological order.
  4. For explicit DAG problems (e.g., longest path, number-of-paths), run the sweep directly.
  5. If the DAG has cycles or negative weights, switch to the appropriate graph algorithm (Dijkstra, Bellman-Ford, BFS).
  6. For reconstruction, store parent[v] alongside $dp[v]$ and walk back from the argmax.
  7. If the state space is large but the actually-reached subset is small (sparse), prefer memoization over topological tabulation.

The measure that guarantees acyclicity is worth naming explicitly. For sequence DPs it is prefix length; for interval DPs it is interval length; for bitmask DPs it is popcount(mask); for tree DPs it is subtree size; for Bellman-Ford it is the layer index (edges used). If you cannot name the measure, you may not have a DAG -- and your recurrence may not terminate. Writing the measure down as a comment next to the recurrence is a cheap sanity gate.

Transfer / Where This Shows Up Later​

  • S3 Software Design. Build systems (Bazel, Buck) compute minimum rebuild sets via topological DP on target DAGs; artifact cache invalidation is a DAG sweep.
  • S5 Networking. BGP best-path selection within an AS is shortest path on a topology DAG-after-loop-prevention; OSPF link-state is Dijkstra, a greedy cousin of DAG DP.
  • S6 Databases. Selinger's System R optimizer (1979) uses bottom-up DP over join subsets -- a DAG of subquery plans whose topological order is "by subset size." Modern DPhyp and DPccp optimizers keep this structure.
  • S7 Architecture. Architecture decision dependency graphs are DAGs; "compute reachable impact of an ADR change" is a reachability DP on this DAG. Service dependency graphs (microservices) are DAGs; "critical path for a request" is literal longest path.
  • Phase 7 AI. Bellman equations $V^(s) = \max_a [R(s,a) + \gamma V^(s')]$ generalize DP-on-DAGs to cyclic state graphs; value iteration is Bellman-Ford with the "layer" being iteration count. Reinforcement learning's credit assignment is DP over the trajectory DAG.

Check Yourself​

  1. Why is longest path in a DAG polynomial, while longest path in a general graph is NP-hard?
  2. Give a DP you have written and describe its implicit DAG of subproblems.
  3. What algorithm handles "shortest path" when the graph has cycles and nonnegative weights?
  4. Why can Bellman-Ford be framed as a DP even though the underlying graph has cycles?
  5. Topologically sort a DAG with $V = 6$, $E = {(1,2), (1,3), (2,4), (3,4), (4,5), (4,6)}$ and list two valid orderings.
  6. Express the LIS recurrence as a DAG-longest-path problem.

Mini Drill or Application​

  1. Implement longest path in a DAG given an edge list. Verify on a small hand-crafted example.
  2. Reformulate LIS as longest path in a DAG and implement the DAG version. Compare its output to a standard LIS on 20 random arrays.
  3. Count the number of monotonic paths from $(0,0)$ to $(m-1, n-1)$ in a grid with obstacles by topological sweep.
  4. Given a task graph with durations and dependencies, compute the critical path (longest path in the DAG) -- the minimum time to finish all tasks. Identify which tasks are on the critical path (zero-slack tasks).
  5. Implement Bellman-Ford as a layered DP and confirm it matches the standard relaxation formulation.
  6. "Can-reach" DP: given a DAG and a set of target vertices, compute for each vertex whether it can reach at least one target.
  7. Implement the 5-vertex longest-path trace from the example above; print $dp$ after each vertex is processed and verify it matches.
  8. Given a DAG of tasks with durations, compute both the earliest start time (forward DP) and the latest start time without delaying the project (backward DP); a task's slack is the difference. Zero-slack tasks form the critical path.

Read This Only If Stuck​

If the DAG framing feels abstract: pick any DP you have written (Fibonacci, LIS, edit distance) and draw its dependency graph on paper for $n = 4$ or $m = n = 3$. Label each node with the state tuple. Draw an arrow from each subproblem to the ones it depends on. You will see a DAG. Now draw a second graph with edges reversed. The first is "who do I depend on"; the second is "who depends on me." Topological fill uses the first; push-style updates use the second. Both are valid DP orderings -- they are just two ways of traversing the same DAG.