Network Flow
Algorithms

What is a flow network?

A directed graph G = (V, E) with two distinguished vertices and a capacity function:

• Source (s) — where flow originates; no incoming flow constraint
• Sink (t) — where flow is consumed; no outgoing flow constraint
• Capacity c(u,v) — maximum flow allowed on edge (u,v); always non-negative
• Flow f(u,v) — the actual flow on edge (u,v)

Formal definition

A flow network is a tuple (G, s, t, c):

G = (V, E)    directed graph
s ∈ V         source vertex
t ∈ V         sink vertex
c: E → R⁺     capacity function

Value of a flow

The total flow leaving the source (equivalently, arriving at the sink):

|f| = Σ f(s,v) - Σ f(v,s)
    = Σ f(v,t) - Σ f(t,v)

s-t Cut

A partition of vertices into sets S and T where s ∈ S and t ∈ T. The capacity of the cut is:

c(S, T) = Σ c(u,v)  for all u ∈ S, v ∈ T

Only edges crossing from S to T count — not edges from T to S.

The theorem (Ford & Fulkerson, 1956)

max |f| = min c(S, T)

Residual graph

Given a flow f, the residual graph Gf shows remaining capacity on each edge:

Forward edge:  c_f(u,v) = c(u,v) - f(u,v)
  (room to push more flow)

Backward edge: c_f(v,u) = f(u,v)
  (room to cancel existing flow)

Augmenting path

A path from s to t in the residual graph Gf. The bottleneck is the minimum residual capacity along the path.

The method (1956)

Ford-Fulkerson(G, s, t):
    initialise f(u,v) = 0 for all edges
    while ∃ augmenting path p in G_f:
        cf(p) = min residual capacity along p
        for each edge (u,v) in p:
            f(u,v) += cf(p)
            f(v,u) -= cf(p)
    return f

Key properties

• Correctness — terminates with max flow when capacities are integers
• Integer capacities — runtime O(E · |f*|) where |f*| is max flow value
• Irrational capacities — may not terminate; can converge to wrong answer
• Path choice matters — poor choices lead to exponential iterations

BFS-based Ford-Fulkerson (1972)

Always choose the shortest augmenting path (fewest edges) using breadth-first search.

Edmonds-Karp(G, s, t):
    initialise f = 0
    while BFS finds path p from s to t in G_f:
        cf(p) = bottleneck of p
        augment flow along p by cf(p)
    return f

Complexity

Level graph and blocking flow (1970)

Dinic's algorithm builds a level graph using BFS and finds blocking flows using DFS.

Dinic(G, s, t):
    while BFS builds level graph L of G_f:
        while ∃ blocking flow f' in L:
            augment f by f'
        rebuild level graph
    return f

Complexity

Level graph construction

1. Run BFS from source s in Gf
2. Assign level d(v) = shortest distance from s
3. Keep only edges (u,v) where d(v) = d(u) + 1
4. Remove dead-end vertices with no path to t

What is a blocking flow?

A flow in the level graph such that every s-t path contains at least one saturated edge. Not necessarily a maximum flow — but simpler to find.

Finding blocking flows

DFS from s:
    advance along unsaturated edges
    if reach t:
        augment along path, retreat
    if stuck at v:
        delete v from level graph
        retreat

• Each advance or retreat takes O(1) amortised
• At most O(E) advances and O(V) retreats per blocking flow

Core concepts

Operations

• Push(u,v) — send min(e(u), cf(u,v)) flow; requires h(u) = h(v) + 1
• Relabel(u) — increase h(u) to min(h(v) + 1) over admissible neighbours

Push-Relabel(G, s, t):
    h(s) = |V|, saturate all edges from s
    while ∃ active vertex u:
        if u has admissible edge (u,v):
            push(u, v)
        else: relabel(u)

Complexity by variant

Gap heuristic

If no vertex has height h, then any vertex with height above h cannot reach the sink. Relabel all such vertices to |V| + 1 — they drain back to source.

Global relabelling

Periodically recompute exact heights using reverse BFS from t. Dramatically reduces wasted pushes in practice.

Relationship to max flow

Special cases

• Shortest path — min-cost flow with d = 1
• Assignment problem — min-cost perfect matching in bipartite graph
• Transportation problem — supply and demand at nodes, costs on edges

The problem

Given a bipartite graph G = (L ∪ R, E), find the largest set of edges with no shared endpoints.

Reduction to max flow

1. Add source s connected to all vertices in L (capacity 1)
2. Add sink t connected from all vertices in R (capacity 1)
3. All original edges have capacity 1
4. Max flow in this network = maximum matching size

Koenig's theorem

Hopcroft-Karp algorithm

Specialised for bipartite matching. Uses BFS to find maximal sets of shortest augmenting paths, then DFS to augment.

Complexity: O(E · √V) — equivalent to Dinic's on unit networks.

Core idea

Maintain feasible vertex labels (potentials) such that:

l(x) + l(y) ≥ w(x,y)   ∀ x ∈ L, y ∈ R

The equality subgraph contains only edges where l(x) + l(y) = w(x,y). A perfect matching in the equality subgraph is optimal.

Algorithm outline

1. Initialise: l(x) = max w(x,y) for left, l(y) = 0 for right
2. For each unmatched left vertex, try augmenting in equality subgraph
3. If no path, adjust labels to expand equality subgraph
4. Repeat until all vertices matched

Complexity

Image segmentation via min-cut

Partition image pixels into foreground (F) and background (B):

1. Create a node per pixel
2. Source s = foreground label; sink t = background label
3. Edge (s, pixel) = likelihood pixel is foreground
4. Edge (pixel, t) = likelihood pixel is background
5. Edge (pixeli, pixelj) = smoothness penalty for different labels
6. Minimum s-t cut gives optimal binary segmentation

Max-flow algorithms

Related problems

Key takeaways

• Flow networks model constrained movement: capacity, conservation, source-to-sink
• Max-flow min-cut theorem connects flow maximisation to cut minimisation via LP duality
• Ford-Fulkerson is foundational; Edmonds-Karp, Dinic's, and push-relabel improve to polynomial time
• Dinic's achieves O(V²E) and is optimal for unit-capacity graphs at O(E√V)
• Push-relabel with heuristics is fastest in practice for dense graphs
• Min-cost flow generalises max flow with edge costs
• Bipartite matching reduces to max flow; Hungarian solves weighted assignment in O(n³)
• Applications: transportation, scheduling, image segmentation, network reliability
• Modelling techniques (vertex splitting, super-sources, lower bounds) are the key practical skill

Recommended reading