Skip to main content

DP on Trees and Graphs

TL;DR​

DP on trees and graphs exploits structure for efficient solutions. Tree DP: Root tree at arbitrary node, compute DP values bottom-up via DFS. Combine subtree solutions for optimal answer. Example: Maximum independent set where dp[u][0] = max value excluding u, dp[u][1] = max value including u. Rerooting: First DFS computes DP for one root, second DFS recomputes for each node as root using parent information. Enables problems requiring all-nodes perspective. DAG DP: Process nodes in topological order to ensure dependencies computed first. Combine solutions from predecessor nodes. Shortest paths as DP: Bellman-Ford treats dp[i] = shortest path to node i as DP state, relaxing edges iteratively. Handles negative weights; detects negative cycles. Tree DP foundation: identify what to compute per subtree, combine subtree results appropriately.

Core Concepts​

Tree DP Structure​

Tree DP solves problems on tree substructures by rooting tree and computing values bottom-up.

Key Characteristics:

  • Root Selection: Pick any node as root (choice doesn't affect answer)
  • Postorder Traversal: Process children before parent to ensure dependencies ready
  • Subtree Independence: Subtree solutions independent of other subtrees
  • Parent Dependency: Parent solution depends on children solutions

State Definition: dp[u][k] where u is node and k represents state (e.g., including vs excluding node).

Rerooting Technique​

Rerooting computes answer for every node as root. Useful when problem requires considering each node as root or center.

Two-Pass Algorithm:

  1. First DFS: Root at arbitrary node, compute bottom-up DP
  2. Second DFS: Recompute DP with parent information, enabling each node as root

Advantage: O(n) per state rather than O(n²) if recomputing from scratch for each root.

DAG DP Principles​

DAG DP processes nodes in topological order, ensuring all predecessors computed before current node.

Workflow:

  1. Compute topological sort
  2. Process nodes in order
  3. For each node, combine solutions from predecessor nodes

No Cycles: DAG property ensures no cycles complicate dependency ordering.

Shortest Paths as DP​

Shortest path algorithms follow DP pattern: dp[i] represents shortest distance to node i, updated by relaxing edges.

Bellman-Ford as DP:

dp[i] = minimum distance from source to node i
After k iterations, dp[i] = shortest path using at most k edges

Dijkstra as greedy DP: Selects node with minimum distance and finalizes it.

Key Algorithms​

Maximum Independent Set in Tree​

Problem: Find maximum weighted independent set (no two adjacent nodes).

State:

  • dp[u][0] = max value in subtree u when u is NOT included
  • dp[u][1] = max value in subtree u when u IS included

Recurrence:

dp[u][0] = sum(max(dp[v][0], dp[v][1])) for all children v
dp[u][1] = node_value[u] + sum(dp[v][0]) for all children v

Insight: If node included, children cannot be included. If node excluded, children can be included or not.

DAG Shortest Path​

Problem: Find shortest path in DAG from source to all nodes.

Approach:

  1. Topological sort all nodes
  2. For each node in topological order, relax all outgoing edges
  3. Complexity: O(V + E)

Bellman-Ford as DP​

Problem: Find shortest path handling negative weights and detecting negative cycles.

DP State: dp[k][i] = shortest path to node i using at most k edges

Recurrence:

dp[k][i] = min(dp[k-1][i], min(dp[k-1][u] + weight(u,i)) for all u->i)

Convergence: If dp[V-1][i] != dp[V][i] for any i, negative cycle exists.

Practical Example​

# Maximum Independent Set in Tree
class TreeDPMaxIndependentSet:
    def __init__(self, n):
        self.graph = [[] for _ in range(n)]
        self.values = [0] * n

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def solve(self, root=0):
        self.dp = [[0, 0] for _ in range(len(self.graph))]
        self.visited = [False] * len(self.graph)
        self.dfs(root)
        return max(self.dp[root][0], self.dp[root][1])

    def dfs(self, u):
        self.visited[u] = True
        self.dp[u][0] = 0  # Max value if u not included
        self.dp[u][1] = self.values[u]  # Max value if u included

        for v in self.graph[u]:
            if not self.visited[v]:
                self.dfs(v)
                # If u not included, child can be included or not
                self.dp[u][0] += max(self.dp[v][0], self.dp[v][1])
                # If u included, child must not be included
                self.dp[u][1] += self.dp[v][0]

# DAG Shortest Path using Topological Sort
def dag_shortest_path(n, edges, source):
    """
    edges: list of (u, v, weight)
    Returns shortest distances from source
    """
    from collections import defaultdict

    graph = defaultdict(list)
    in_degree = [0] * n

    for u, v, w in edges:
        graph[u].append((v, w))
        in_degree[v] += 1

    # Topological sort using Kahn's algorithm
    queue = [i for i in range(n) if in_degree[i] == 0]
    topo_order = []

    for u in queue:
        for v, w in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
        topo_order.append(u)

    # DP: shortest path
    dist = [float('inf')] * n
    dist[source] = 0

    for u in topo_order:
        if dist[u] != float('inf'):
            for v, w in graph[u]:
                dist[v] = min(dist[v], dist[u] + w)

    return dist

# Bellman-Ford as DP
def bellman_ford(n, edges, source):
    """
    edges: list of (u, v, weight)
    Returns shortest distances; detects negative cycles
    """
    dist = [float('inf')] * n
    dist[source] = 0

    # Relax edges n-1 times
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # Check for negative cycle
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None  # Negative cycle detected

    return dist

# Tests
tree = TreeDPMaxIndependentSet(5)
tree.values = [3, 2, 1, 3, 4]
tree.add_edge(0, 1)
tree.add_edge(0, 2)
tree.add_edge(1, 3)
tree.add_edge(1, 4)
print(tree.solve())  # Maximum independent set

edges = [(0,1,4), (0,2,2), (1,2,1), (1,3,5), (2,3,3)]
print(dag_shortest_path(4, edges, 0))  # DAG shortest path

edges_bf = [(0,1,-1), (0,2,4), (1,2,3), (1,3,2), (2,3,-5)]
print(bellman_ford(4, edges_bf, 0))  # Bellman-Ford

Common Pitfalls​

warning

Incorrect tree rooting: Different roots can lead to wrong answers if tree structure not handled properly. Always verify consistent parent-child direction.

Forgetting to unvisit in tree DP: Unlike graph DFS, tree traversal needs visited tracking only for rooted trees. Unrooted trees need parent pointers.

Wrong topological order in DAG DP: Topological sort must ensure all predecessors processed before node. Verify sort output or use DFS-based topological sort.

Negative cycle not detected: Bellman-Ford requires one more iteration to detect negative cycles. Don't skip this check.

Rerooting complexity: Naive rerooting from scratch is O(n²). Proper two-pass rerooting is O(n) but requires careful state management with parent contributions.

Forgetting edge weights: Many graph problems include weights. Ensure transitions use correct weight values.

Self-Check​

  1. Why must tree DP use DFS postorder traversal? What happens with preorder?
  2. In rerooting technique, what information does the second DFS compute that the first DFS missed?
  3. How does topological sort enable DP on DAGs? What would happen without it?

One Takeaway​

info

Tree and graph DP exploits structural properties for efficient solutions. Tree DP works bottom-up: compute solutions for subtrees, combine for parent. Rerooting enables all-nodes perspective with O(n) work per state. DAG DP relies on topological ordering to ensure dependency satisfaction. Shortest paths illustrate how classical algorithms follow DP patterns. Mastering these structures unlocks solutions to countless optimization problems on graphs and trees. The key is identifying problem structure—trees suggest postorder DFS, DAGs suggest topological sort, shortest paths suggest relaxation patterns.

References​

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
  • Tarjan, R. E. (1972). "Depth-first search and linear graph algorithms." SIAM Journal on Computing, 1(2), 146-160.