Maximum Flow — Edmonds-Karp Prevents Billion Iterations

Maximum flow is one of the most underrated algorithmic primitives in combinatorial optimisation. Bipartite matching, project selection with dependencies, image segmentation, airline crew scheduling, bandwidth allocation — all reduce cleanly to max flow. When you see a problem involving 'maximum throughput through a constrained network', max flow is almost always the right abstraction.

Ford-Fulkerson (1956) established the augmenting-path framework. Edmonds-Karp (1972) fixed its fatal flaw: always pick the shortest augmenting path using BFS. That single constraint moved worst-case complexity from 'possibly exponential' to 'provably O(VE²)' — and that guarantee is what separates a toy implementation from something you can actually deploy.

What is the Maximum Flow Problem?

The **maximum flow problem** asks: given a directed graph G = (V, E) where every edge (u, v) has a non-negative integer capacity c(u, v), and two designated nodes — a source s and a sink t — what is the maximum total flow that can be routed from s to t simultaneously?

The value of the flow is the total amount leaving s (or equivalently, arriving at t).

Why greedy path selection fails. The naive approach — find a path, push as much flow as possible, repeat — is wrong. Paths share edges. A locally optimal choice on the first path can permanently block a globally better combination of paths. This is exactly why the residual graph and backward edges exist.

The hidden power: max flow solves min cut for free. By the max-flow min-cut theorem, the maximum flow value equals the capacity of the minimum cut — the minimum total capacity of edges you'd need to remove to disconnect s from t entirely. One algorithm, two answers. That duality is what makes max flow worth learning deeply.

What is the Ford-Fulkerson Method?

Ford-Fulkerson (Lester Ford and Delbert Fulkerson, 1956) is not a single algorithm — it is a method or framework. It defines what to do but deliberately leaves open how to find the augmenting path.

The Ford-Fulkerson loop: 1. Find any path from s to t in the residual graph with available capacity 2. Push flow equal to the bottleneck (minimum residual capacity on that path) 3. Update the residual graph (forward edges decrease, backward edges increase) 4. Repeat until no path from s to t exists

The framework is correct. The complexity depends entirely on step 1.

With DFS path selection on a graph with integer capacities, Ford-Fulkerson terminates — but can require O(f) augmentations where f is the total max flow value. If f = 10⁹, that is a billion iterations. On adversarial graphs with large capacities, DFS Ford-Fulkerson is practically useless.

Ford-Fulkerson is best thought of as the theoretical foundation. In practice, you always instantiate it with a specific path-finding strategy. The most important instantiation is Edmonds-Karp.

What is the Edmonds-Karp Algorithm?

Edmonds-Karp (Jack Edmonds and Richard Karp, 1972) is Ford-Fulkerson with one specific, decisive constraint: always find the shortest augmenting path using BFS.

That single constraint — fewest hops, found by BFS — changes the complexity from O(Ef) to O(VE²): polynomial time, always, regardless of capacity values.

Why does it work? BFS guarantees that the distance from s to any node in the residual graph is non-decreasing across iterations. This bounds the total number of augmentations to O(VE), and since each BFS is O(E), the total is O(VE²).

In one sentence: Edmonds-Karp is the correct, production-safe implementation of the maximum flow algorithm for most use cases.

When to use Edmonds-Karp vs alternatives: - Edmonds-Karp O(VE²) — default choice; clean implementation, polynomial guaranteed, fine for V ≤ 500 - Dinic's O(V²E) — faster in practice on dense graphs; use when profiling shows Edmonds-Karp is a bottleneck - Push-relabel O(V²√E) — best theoretical complexity for general graphs; complex to implement correctly - Ford-Fulkerson with DFS — never in production; textbook examples only

For 99% of interview questions and most real systems, Edmonds-Karp is the right answer.

Residual Graphs — The Core Data Structure

Every max flow algorithm lives or dies on its residual graph implementation. Get this wrong and the algorithm silently produces incorrect results.

The residual graph contains both of these for every original edge. It is updated after each augmentation — never recomputed from scratch.

Why backward edges exist — the undo mechanism.

An earlier greedy choice may have used an edge that blocks a better global solution. The backward edge lets the algorithm redirect previously-committed flow: pushing flow along (v, u) in the residual graph effectively cancels f units of flow from the earlier (u, v) assignment. Without backward edges, you cannot recover from suboptimal early choices and the algorithm gets permanently stuck below the true maximum.

The initialisation rule is fixed and non-negotiable: every backward edge starts at 0. The update rule is equally fixed: when you push f units along (u, v), do residual[u][v] -= f and residual[v][u] += f. Both updates happen atomically — one without the other is a bug.

Edmonds-Karp: Step by Step

Here are the five steps, precisely stated:

Step 1 — Build the residual graph Copy the original graph adjacency structure. For every directed edge (u, v) with capacity c, add the reverse edge (v, u) with residual capacity 0 if it does not already exist. This is a one-time setup before the main loop.

Step 2 — BFS from s to t Run BFS on the current residual graph. Only traverse edges with residual capacity > 0. Record the parent of each visited node. If t is never reached, the algorithm terminates — no augmenting path exists and the current flow is maximum.

Step 3 — Find the bottleneck Reconstruct the path from t back to s using the parent map. The bottleneck is min(residual[u][v]) across all edges on the path. This is the maximum flow increment for this iteration.

This is the atomic update. Both lines are required. The backward edge update is what enables future rerouting.

Step 5 — Accumulate and repeat max_flow += bottleneck. Go to Step 2.

The critical insight about BFS vs DFS: BFS produces the shortest path (fewest edges). Edmonds and Karp proved that with shortest-path augmentation, the distance from s to any node in the residual graph is non-decreasing across iterations. This limits the total augmentations to O(VE) — making the whole algorithm O(VE²) regardless of capacity values. DFS has no such guarantee.

Proof of Non-decreasing Distances in Edmonds-Karp

Why does BFS augmentation bound the number of iterations to O(VE)? The core lemma is: during Edmonds-Karp, for every vertex v, the shortest-path distance d(v) from s in the residual graph is non-decreasing across augmentations.

Proof outline, by contradiction: Let d_f(v) be the distance just before an augmentation along path P (bottleneck edge e). Suppose after augmentation, the distance to some vertex x strictly decreases: d_f'(x) < d_f(x). Consider the moment when d_f'(x) first drops. Since the only changes to the residual graph are along P, the new shorter path must use a backward edge of P (because forward edges only lose capacity). Let (u, v) be the first backward edge on the new path, so that d_f'(u) = d_f'(v) - 1 (distance via BFS ordering). Because (u, v) is a backward edge, the original edge (v, u) was in P. Before augmentation, d_f(u) ≤ d_f(v) - 1 by the BFS shortest-path property? Wait, careful: The original BFS distances before augmentation satisfy d_f(v) = d_f(u) + 1 because P is a shortest path. After augmentation, the residual graph now has a backward edge (u, v) with positive capacity. In the new shorter path, the distance to u is at least d_f'(u). Contradiction arises by using the triangle inequality and assumed decrease.

The formal lemma: If a vertex v has its distance decrease, then there exists some edge (u, v) used in the new path that was a backward edge of the augmenting path. By construction, d_f(u) = d_f(v) - 1 from the previous BFS (since (v, u) was on the shortest path). But after augmentation, d_f'(v) = d_f'(u) + 1. Combining leads to d_f'(v) ≥ d_f(v), contradiction. Therefore distances can never decrease.

Implication: Each vertex can experience at most V distance increases (since distance max is V). Each augmenting path contains at least one edge whose distance to s is guaranteed to increase after a certain number of times? Actually, each edge (u, v) can become a bottleneck at most O(V) times because each time the distance to either u or v increases. So augmentations ≤ O(VE).

This proof is what separates an exponential heuristic from a polynomial algorithm. Edmonds and Karp were the first to formalise it, and it remains the foundational argument for bounded augmentation counts in BFS-based augmenting path algorithms.

Worked Example — Tracing Every Iteration

Graph: `` s → a (cap 10) s → b (cap 10) a → t (cap 10) a → b (cap 2) b → t (cap 10) ` Initial residual graph (all backward edges start at 0): ` s→a:10 a→s:0 s→b:10 b→s:0 a→t:10 t→a:0 a→b: 2 b→a:0 b→t:10 t→b:0 ``

Iteration 1: - BFS queue: [s] → dequeue s, enqueue a (res=10), enqueue b (res=10) - Dequeue a, enqueue t (res=10). t reached — stop BFS. - Shortest path: s → a → t (2 hops) - Bottleneck: min(10, 10) = 10 - Update: s→a: 10→0, a→s: 0→10; a→t: 10→0, t→a: 0→10 - max_flow = 10

Iteration 2: - BFS queue: [s] → dequeue s; s→a has residual 0 (skip); enqueue b (res=10) - Dequeue b, enqueue t (res=10). t reached — stop BFS. - Shortest path: s → b → t (2 hops) - Bottleneck: min(10, 10) = 10 - Update: s→b: 10→0, b→s: 0→10; b→t: 10→0, t→b: 0→10 - max_flow = 20

Iteration 3: - BFS queue: [s] → dequeue s; s→a residual=0 (skip), s→b residual=0 (skip) - Queue empties. t never reached. - Terminate. Maximum flow = 20. ✓

Observation: edge a→b (cap 2) was never used. BFS found two direct 2-hop paths and saturated both. The a→b edge would only appear in a solution if one of those direct paths were blocked — and here, both were available from the start. This is exactly the kind of clean, predictable behaviour that makes Edmonds-Karp the default choice.

Python Implementation

The code below maps directly to the five steps above. Every comment references the step it implements.

from collections import deque

def edmonds_karp(graph: dict, source: str, sink: str) -> int:
    """
    Edmonds-Karp: Ford-Fulkerson with BFS augmenting paths.
    graph: {node: {neighbour: capacity}}
    Returns maximum flow from source to sink. O(VE^2).
    """
    # Step 1: build residual graph
    # Copy original capacities; add backward edges initialised to 0
    residual = {u: dict(v_cap) for u, v_cap in graph.items()}
    for u in graph:
        for v in graph[u]:
            if v not in residual:
                residual[v] = {}
            if u not in residual[v]:
                residual[v][u] = 0  # backward edge — must exist

    def bfs_augmenting_path():
        """Steps 2–3: BFS for shortest path, return path + bottleneck."""
        parent = {source: None}
        queue = deque([source])

        while queue:
            node = queue.popleft()
            if node == sink:
                break
            for neighbour, cap in residual[node].items():
                if neighbour not in parent and cap > 0:
                    parent[neighbour] = node
                    queue.append(neighbour)

        if sink not in parent:
            return None, 0  # no augmenting path — algorithm terminates

        # Reconstruct path and find bottleneck
        path, node = [], sink
        while node != source:
            prev = parent[node]
            path.append((prev, node))
            node = prev

        bottleneck = min(residual[u][v] for u, v in path)
        return path, bottleneck

    max_flow = 0
    while True:
        path, bottleneck = bfs_augmenting_path()
        if path is None:
            break

        # Step 4: augment — both updates are mandatory
        max_flow += bottleneck
        for u, v in path:
            residual[u][v] -= bottleneck  # forward: capacity consumed
            residual[v][u] += bottleneck  # backward: undo capacity created

    return max_flow  # Step 5 complete


graph = {
    's': {'a': 10, 'b': 10},
    'a': {'t': 10, 'b': 2},
    'b': {'t': 10, 'a': 0},
    't': {}
}
print(edmonds_karp(graph, 's', 't'))  # 20

The Max-Flow Min-Cut Theorem

The maximum flow from s to t equals the capacity of the minimum cut.

A cut partitions all nodes into two sets: S (containing s) and T (containing t). The cut's capacity is the sum of capacities of all edges crossing from S to T (not T to S — direction matters).

The minimum cut is the partition that minimises this total crossing capacity. It represents the true bottleneck of the network: the set of edges whose removal would disconnect s from t at lowest cost.

Reading the minimum cut from Edmonds-Karp's output: After the algorithm terminates, run BFS on the final residual graph from s. Every node reachable from s belongs to set S; every unreachable node belongs to set T. The edges from S to T in the original graph are all saturated (residual capacity = 0). These are your minimum cut edges.

Why this duality is powerful: - Network reliability: the minimum cut identifies the least-resilient links — removing them disconnects the network at minimum cost - Bipartite matching: by König's theorem, maximum bipartite matching = max flow on a unit-capacity graph; min cut = minimum vertex cover - Project selection: model projects as nodes with profit/dependency edges; max flow gives the optimal project set - Image segmentation: pixels are nodes; intensity differences are capacities; min cut separates foreground from background

This single theorem is why max flow shows up in computer vision, operations research, computational biology, and network engineering. It is not just an algorithm — it is a modelling tool.

Complexity — When to Use Which Algorithm

Why Edmonds-Karp is O(VE²): BFS guarantees shortest paths. A key lemma proves that under BFS augmentation, the distance d(s, v) in the residual graph is non-decreasing for every node v. Since distances are bounded by V, and each 'distance increase' event can happen at most O(V) times per edge, the total augmentations are bounded by O(VE). Each BFS costs O(E). Total: O(VE²).

Decision rule for production: 1. Default to Edmonds-Karp — clean implementation, O(VE²) guarantee, fine for V ≤ 500 2. Profile before switching — Dinic's is faster in practice but more complex to implement correctly 3. Never use Ford-Fulkerson with DFS in production code — the exponential risk is not worth it

Interview answer: Edmonds-Karp is what interviewers expect. State the O(VE²) complexity, explain why BFS prevents the exponential blow-up, and mention that Dinic's exists for cases where you need better practical performance.