Introduction

In a static graph, a maximum-flow algorithm solves one fixed network. In a dynamic graph, edges or capacities change over time, so the real challenge is how much of the previous solution can be reused instead of recomputing the whole flow from scratch after every update.

Start with the Static Problem

A flow network has:

• a source s
• a sink t
• edge capacities
• a feasible flow that obeys capacity and conservation constraints

In a static setting, algorithms such as Edmonds-Karp, Dinic, and Push-Relabel compute a max flow once.

A small Edmonds-Karp implementation illustrates the baseline problem:

1from collections import deque
2
3
4def bfs(capacity, flow, s, t, parent):
5    n = len(capacity)
6    visited = [False] * n
7    queue = deque([s])
8    visited[s] = True
9
10    while queue:
11        u = queue.popleft()
12        for v in range(n):
13            residual = capacity[u][v] - flow[u][v]
14            if not visited[v] and residual > 0:
15                visited[v] = True
16                parent[v] = u
17                if v == t:
18                    return True
19                queue.append(v)
20    return False
21
22
23def max_flow(capacity, s, t):
24    n = len(capacity)
25    flow = [[0] * n for _ in range(n)]
26    parent = [-1] * n
27    total = 0
28
29    while bfs(capacity, flow, s, t, parent):
30        path_flow = float("inf")
31        v = t
32        while v != s:
33            u = parent[v]
34            path_flow = min(path_flow, capacity[u][v] - flow[u][v])
35            v = u
36
37        v = t
38        while v != s:
39            u = parent[v]
40            flow[u][v] += path_flow
41            flow[v][u] -= path_flow
42            v = u
43
44        total += path_flow
45
46    return total, flow

Dynamic max flow starts from this idea and asks how updates change the residual graph.

What Changes in a Dynamic Graph

A dynamic flow network may experience:

• edge insertion
• edge deletion
• capacity increase
• capacity decrease

Each update can invalidate part of the old solution. But not every update destroys everything.

For example:

• an added edge may create new augmenting paths
• a capacity increase may allow more flow without changing existing feasible flow
• a capacity decrease can make the current flow infeasible and require repairs

That is why dynamic maximum flow is usually described in incremental, decremental, or fully dynamic variants.

Incremental Updates Are Easier

If an edge is added or a capacity increases, the old flow remains feasible. It may no longer be maximum, but it is still a valid starting point.

That means a practical dynamic strategy is:

1. keep the current residual network
2. apply the edge or capacity increase
3. search for new augmenting paths from the old residual graph

In many cases, this is much cheaper than recomputing from zero.

def increase_capacity(capacity, u, v, delta):
    capacity[u][v] += delta

After that update, you can continue augmentation starting from the existing flow.

Decremental Updates Are Harder

Decreasing capacity or deleting an edge is more difficult because the current flow may become infeasible.

If an edge currently carries 7 units of flow and its capacity drops to 3, then 4 units must be rerouted or canceled. The algorithm now has two jobs:

• repair feasibility
• restore maximality if possible

That is why decremental dynamic max flow is much more delicate than the incremental case.

A common practical approach is to identify overflow on the changed edge, send flow backward in the residual graph where possible, and then re-augment. In theory and in advanced algorithms, specialized data structures may help, but in production systems many teams still fall back to partial or full recomputation for complex decremental cases.

Residual Graph Reuse Is the Core Idea

The residual graph is the key object to preserve. It tells you which augmenting or canceling moves are still possible after a change.

When the graph changes slightly, throwing away the entire residual structure is often wasteful. Dynamic algorithms try to update the residual graph locally and then resume search.

This is the main reason dynamic flow can outperform repeated full recomputation when updates are small and frequent.

Theory Versus Practical Engineering

There is deep research on dynamic max flow with advanced data structures and update-time guarantees. But in day-to-day engineering, the right choice often depends on update patterns.

A reasonable rule is:

• for rare updates, recompute from scratch
• for frequent small capacity increases, reuse the current flow and residual graph
• for complex deletions, consider whether the maintenance logic is worth the implementation cost

In other words, dynamic max flow is not one algorithm. It is a family of strategies that trade implementation complexity for update performance.

Common Pitfalls

A common mistake is assuming every graph update requires a full recomputation. That is often unnecessary for incremental changes.

Another issue is assuming deletions are as easy as insertions. They are not. Decremental updates can break feasibility, not just optimality.

Developers also sometimes preserve the current flow but forget to update the residual graph consistently, which leads to invalid augmenting searches.

Finally, be careful with benchmark claims. A dynamic method only helps if the update pattern matches the assumptions it was designed for.

Summary

• Dynamic max flow tries to reuse previous work after graph updates.
• Capacity increases and edge insertions are usually easier to handle incrementally.
• Capacity decreases and deletions are harder because they can break feasibility.
• The residual graph is the main structure worth preserving across updates.
• In practice, the right approach depends on update frequency and implementation cost.