12.2 Residual Graphs

Problem

Suppose you have already constructed a valid flow in a network. You discover another path from the source to the sink and want to increase the total flow.

A natural approach is to send additional flow through the newly discovered path.

Unfortunately, previous decisions may block better solutions.

Consider the network:

Edge	Capacity
S → A	10
S → B	10
A → B	5
A → T	10
B → T	10

Suppose the first augmenting path chosen is:

S → A → B → T

and 5 units are sent through it.

The resulting flow becomes:

Edge	Flow
S → A	5
A → B	5
B → T	5

Now imagine later discovering:

S → A → T

and

S → B → T

A maximum flow of 20 clearly exists, yet some capacity is trapped inside the earlier decision.

We need a mechanism that allows previously assigned flow to be revised.

Solution

Introduce a residual graph.

A residual graph describes every possible way the current flow can be modified.

Instead of representing what flow currently exists, it represents what additional actions remain possible.

The residual graph becomes the working graph for all maximum-flow algorithms.

Residual Capacity

Given an edge:

u → v

with capacity:

c(u,v)

and current flow:

f(u,v)

the remaining forward capacity is:

c(u,v) - f(u,v)

This quantity is called the residual capacity.

Example:

Capacity	Current Flow	Residual Capacity
10	4	6
10	10	0
10	0	10

The residual graph contains a forward edge whenever residual capacity is positive.

Reverse Edges

Residual graphs introduce a second concept.

Suppose:

A → B

currently carries:

5

units of flow.

Those 5 units could potentially be removed later.

To represent this possibility, the residual graph adds:

B → A

with capacity:

5

This reverse edge represents the ability to cancel previously assigned flow.

This is the key insight behind modern flow algorithms.

Example

Consider:

Edge	Capacity
S → A	10
A → T	10

Current flow:

Edge	Flow
S → A	6
A → T	6

Residual graph:

Residual Edge	Capacity
S → A	4
A → S	6
A → T	4
T → A	6

The forward edges represent unused capacity.

The reverse edges represent removable flow.

Visualizing Residual Networks

Original network:

S --10--> A --10--> T

Current flow:

S --6--> A --6--> T

Residual network:

S --4--> A
S <--6-- A

A --4--> T
A <--6-- T

Notice that residual edges describe possible modifications rather than actual flow.

Why Reverse Edges Matter

Consider:

S → A → B → T

Suppose 5 units are sent.

Later we discover:

S → B → T

and

S → A → T

which together would yield a larger total flow.

The residual graph allows:

B → A

to appear as a reverse edge.

Traversing:

S → B → A → T

means:

1. Add flow on S → B
2. Remove flow from A → B
3. Add flow on A → T

The total flow increases without violating any constraints.

Without reverse edges, Ford-Fulkerson would become trapped in many suboptimal configurations.

Residual Paths

An augmenting path is any source-to-sink path in the residual graph.

Example:

S → A → T

Residual capacities:

Edge	Residual
S → A	6
A → T	4

The path bottleneck equals:

min(6, 4) = 4

Therefore 4 additional units can be pushed through the path.

Updating Flow

Suppose we augment by:

δ = 4

For every forward edge:

flow += δ

For every reverse edge:

flow -= δ

This simple rule automatically handles flow cancellation.

Residual Graph Construction

Given a flow network:

For every edge:

u → v

with capacity:

c

and flow:

f

Add:

Forward residual edge:

u → v
capacity = c - f

if:

c - f > 0

Add reverse residual edge:

v → u
capacity = f

if:

f > 0

Data Structure

Most implementations store both edges explicitly.

A common structure:

Edge {
    to
    capacity
    reverse_index
}

When flow is pushed:

forward.capacity -= pushed
reverse.capacity += pushed

This makes updates O(1).

Almost every competitive programming and production max-flow implementation uses this pattern.

Key Invariant

At every moment:

Residual Capacity
=
Original Capacity - Current Flow

for forward edges.

And:

Reverse Residual Capacity
=
Current Flow

for reverse edges.

Maintaining this invariant guarantees correctness.

Complexity Impact

Residual graphs allow:

• Incremental improvement
• Flow cancellation
• Efficient updates
• Proof of correctness

Without residual networks, maximum-flow algorithms would require rebuilding entire solutions repeatedly.

Instead, every augmentation becomes a local update.

This transforms maximum-flow computation from a difficult global optimization problem into a sequence of manageable graph searches.

Common Mistakes

Forgetting Reverse Edges

This is the most common bug.

Without reverse edges, many valid augmenting paths disappear.

The algorithm may stop before reaching maximum flow.

Updating Only Forward Capacity

Whenever flow changes:

forward -= pushed
reverse += pushed

must both occur.

Updating one side alone corrupts the residual network.

Confusing Residual Capacity with Flow

Residual capacity measures available modification.

It does not measure current flow.

The two quantities serve different purposes.

Traversing Original Edges

Maximum-flow algorithms search residual graphs, not original graphs.

Using the original graph misses opportunities created by reverse edges.

Takeaway

Residual graphs are the central data structure of network flow algorithms.

They encode every valid modification of the current solution through:

• Forward residual edges representing unused capacity
• Reverse residual edges representing removable flow

Every augmenting-path algorithm, including Ford-Fulkerson, Edmonds-Karp, Dinic, and many advanced variants, operates on residual networks. Once the residual graph contains no path from source to sink, the current flow is guaranteed to be maximum. The next recipe uses this idea to develop the first complete maximum-flow algorithm: Ford-Fulkerson.