✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-183

Dynamic Programming on Trees and Graphs

Understand how dynamic programming solves complex tree and graph problems by combining results from smaller states while respecting the structure of the underlying data.

Explanation

Overview

Dynamic Programming on Trees and Graphs applies dynamic programming techniques to problems whose input is represented as a tree or graph. A solution is constructed by defining states for vertices, subtrees, paths, or other graph structures and combining smaller results according to their relationships.

Key concepts

Tree traversal; Rooted-tree states; Postorder processing; Topological ordering; State transitions; Parent-child relationships

Variables

G: The input graph.; V: The set of vertices in the graph.; E: The set of edges in the graph.; u: The current vertex being processed.; v: A neighboring vertex or child of u.; dp[u]: The dynamic programming state associated with vertex u.

Complexity

treeDP: O(V) time and O(V) auxiliary space for a tree when every vertex and edge is processed a constant number of times.; dagDynamicProgramming: Often O(V + E) time when each vertex and edge is processed a constant number of times in topological order.; generalGraphDP: Depends on the state definition and may be exponential when states represent subsets of vertices or other large combinations.

Example

problem: Find the maximum sum of selected tree nodes when no two selected nodes are directly connected.; tree: root: 1; children: 1: 2; 3; 2: 4; 5; states: take[u]: Maximum sum in the subtree rooted at u when u is selected.; skip[u]: Maximum sum in the subtree rooted at u when u is not selected.; transitions: take[u]: value[u] + sum(skip[v]) for every child v.; skip[u]: sum(max(take[v], skip[v])) for every child v.; output: maximumSum: 18; selectedNodes: 1; 4; explanation: Selecting node 1 prevents selecting its children 2 and 3, but permits selecting suitable descendants. The selected nodes 1, 4, 5, and 6 have a total value of 20, so the maximum sum for this example is 20.

Pseudocode

function treeDP(u, parent):
take = value[u]
skip = 0
for v in adjacency[u]:
if v != parent:
child = treeDP(v, u)
take = take + child.skip
skip = skip + max(child.take, child.skip)
return {take: take, skip: skip}

Applications

Tree independent-set problems.; Tree diameter and path optimization.; DAG shortest paths.; Scheduling with dependency graphs.; Network optimization.; Subset-based graph problems.

Variables

G

The input graph.

V

The set of vertices in the graph.

E

The set of edges in the graph.

U

The current vertex being processed.

V

A neighboring vertex or child of u.

Dp[u]

The dynamic programming state associated with vertex u.

Parent[u]

The parent of u in a rooted tree, when a root and parent relationship are defined.

Example or application

Problem

Find the maximum sum of selected tree nodes when no two selected nodes are directly connected.

Tree

Root

1

Children

1

  • 2

  • 3

2

  • 4

  • 5

3

  • 6

Values

1

5

2

3

3

4

4

6

5

2

6

7

States

Take[u]

Maximum sum in the subtree rooted at u when u is selected.

Skip[u]

Maximum sum in the subtree rooted at u when u is not selected.

Transitions

Take[u]

value[u] + sum(skip[v]) for every child v.

Skip[u]

sum(max(take[v], skip[v])) for every child v.

Output

Maximum Sum

18

Selected Nodes

  • 1

  • 4

  • 5

  • 6

Explanation

Selecting node 1 prevents selecting its children 2 and 3, but permits selecting suitable descendants. The selected nodes 1, 4, 5, and 6 have a total value of 20, so the maximum sum for this example is 20.

Definition

Dynamic Programming on Trees and Graphs applies dynamic programming techniques to problems whose input is represented as a tree or graph. A solution is constructed by defining states for vertices, subtrees, paths, or other graph structures and combining smaller results according to their relationships.

Mathematical Representation

For a rooted tree, a common pattern is dp[u] = combine(localValue[u], dp[v] for each child v of u). The exact transition depends on the problem and its constraints.

Approaches

Tree DP

Roots the tree and computes each node's state after processing its children, commonly using postorder traversal.

Memoization

Stores results for previously computed vertices or graph states.

Iterative Traversal

Uses an explicit stack or queue to avoid recursive call-depth limitations.

Dag Dynamic Programming

Processes a directed acyclic graph in topological order so the states of predecessors are available before a vertex is processed.

Graph State DP

Defines states over subsets, paths, or other graph properties for problems that cannot be solved with a single value per vertex.

Pseudocode

function treeDP(u, parent):
take = value[u]
skip = 0
for v in adjacency[u]:
if v != parent:
child = treeDP(v, u)
take = take + child.skip
skip = skip + max(child.take, child.skip)
return {take: take, skip: skip}

Complexity

Tree DP

O(V) time and O(V) auxiliary space for a tree when every vertex and edge is processed a constant number of times.

Dag Dynamic Programming

Often O(V + E) time when each vertex and edge is processed a constant number of times in topological order.

General Graph DP

Depends on the state definition and may be exponential when states represent subsets of vertices or other large combinations.

Key Concepts

  • Tree traversal

  • Rooted-tree states

  • Postorder processing

  • Topological ordering

  • State transitions

  • Parent-child relationships

  • Graph cycles and dependency management

Advantages

  • Solves many tree optimization problems efficiently.

  • Reuses results from smaller subtrees or graph states.

  • Supports problems involving paths, selections, and connectivity.

  • Can achieve linear complexity for suitable tree and DAG problems.

Limitations

  • A valid state definition and transition must be designed for each problem.

  • A general graph may contain cycles, making simple dependency-based evaluation impossible.

  • Some graph dynamic programming problems require exponentially many states.

  • Recursive implementations can encounter stack-depth limitations on deep trees.

  • The complexity depends strongly on the graph structure and the number of states.

Applications

  • Tree independent-set problems.

  • Tree diameter and path optimization.

  • DAG shortest paths.

  • Scheduling with dependency graphs.

  • Network optimization.

  • Subset-based graph problems.

Related Topics

  • Dynamic Programming

  • Depth-First Search

  • Breadth-First Search

  • Topological Sorting

  • Tree Traversal

  • Graph Algorithms

Practice Question

Why is postorder traversal commonly used in tree dynamic programming?

Practice Answer

Because it processes children before their parent, allowing the parent's state to use already-computed child states.

Learning Objectives

  • Explain the central idea and purpose of dynamic programming on trees and graphs.

  • Identify the assumptions, inputs, and conditions relevant to dynamic programming on trees and graphs.

  • Evaluate an application of dynamic programming on trees and graphs for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Dynamic Programming Applications

Suggest a correction or source · More in Algorithms & Data Structures