Maximum Flow

The Maximum Flow problem asks: given a directed graph with edge capacities and a designated source s and sink t, what is the largest amount of “stuff” (water, packets, traffic, units of supply) that can simultaneously flow from s to t without exceeding any edge’s capacity? The Ford-Fulkerson method (Ford & Fulkerson, 1956) is the foundational meta-algorithm — not a single fully-specified algorithm — for solving it: repeatedly find a path in the residual graph that admits more flow, push as much as that path allows, update the residuals, and stop when no such path exists. Different choices for “find a path” yield different concrete algorithms with vastly different complexities — naive depth-first search can fail to terminate on irrational capacities, Edmonds-Karp uses Breadth-First Search to give O(V·E²), Dinic’s Algorithm uses level graphs for O(V²·E), and so on. The framework also underpins the celebrated Min-Cut Max-Flow Theorem and reduces a remarkably broad class of optimization problems (including Bipartite Matching, image segmentation, and project selection) to flow.

1. Intuition — Pipes, Water, and the Residual Trick

Picture a network of water pipes. Each pipe (directed edge u → v) has a capacity c(u, v), the maximum gallons-per-second it can carry. Water enters at a single source s (a reservoir) and leaves at a single sink t (a city). The question is: how much water can the city drink at peak rate? You’d guess “find a path from reservoir to city, send as much as the narrowest pipe on that path allows, and that’s it” — and for a single path that’s right. But networks have multiple paths, and they share pipes. Worse, the right answer often requires rerouting earlier decisions: you might saturate a pipe with one path, only to realize later you should have used that capacity for a different path, freeing up shared downstream capacity.

The genius of Ford-Fulkerson is the residual graph, which makes “rerouting” a forward operation. After you push f units along edge u → v (capacity c), two things happen:

1. The remaining forward capacity becomes c − f (less room going forward).
2. A backward “anti-edge” v → u gains f units of capacity, representing the option to undo that flow if a better routing emerges.

Concretely, if a future path arrives at v and wants to reach somewhere reachable from u, it can take the backward edge v → u — which physically corresponds to redirecting some of the previous flow away from the pipe u → v. The combined effect on the original network is exactly a different flow distribution. This algebraic trick converts the messy “did I make the right choice five iterations ago?” question into a simple structural one: as long as the residual graph contains any path from s to t, more flow is possible. When no such path exists, you are provably optimal.

The “child analogy” is: imagine you mailed a package via Route A, then realize Route B would have been better. Instead of recalling the package and shipping it on Route B (slow), you can issue a cancellation slip that travels backward along Route A undoing the original shipment, and that cancellation is itself a thing you can chain into Route B. The residual edge v → u is exactly that cancellation slip.

2. Formal Setup

A flow network G = (V, E) is:

• A directed graph with vertex set V and edge set E ⊆ V × V.
• A capacity function c : V × V → ℝ_{≥0}, where c(u, v) = 0 if (u, v) ∉ E.
• Two distinguished vertices: a source s ∈ V and a sink t ∈ V, with s ≠ t.

A flow is a function f : V × V → ℝ satisfying three axioms:

1. Capacity constraint: 0 ≤ f(u, v) ≤ c(u, v) for every (u, v) (you can’t send more than the pipe holds, and we treat flow as non-negative on each forward edge — see the antisymmetry sidebar below).
2. Skew symmetry / antisymmetry (textbook formulation): f(u, v) = −f(v, u). This is a bookkeeping convenience: pushing 5 units u → v is the same as pushing −5 units v → u. Many implementations omit this and work with non-negative f plus explicit reverse edges.
3. Flow conservation: for every vertex v ∉ {s, t}, Σ_u f(u, v) = Σ_w f(v, w). Whatever flows in must flow out — vertices are not reservoirs.

The value of the flow is |f| = Σ_v f(s, v) = Σ_u f(u, t) — the net amount leaving the source (equivalently, entering the sink). The maximum flow problem asks for a flow f* of maximum value.

Antisymmetry vs explicit reverse edges

CLRS uses the antisymmetric convention (f(u, v) = −f(v, u)) which gives clean math but is awkward in code. Most implementations represent flow as a non-negative number per edge and store explicit reverse edges (initially with capacity 0) in the residual graph. The two formulations are equivalent.

2.1 The Residual Graph

Given a flow f, the residual capacity of an edge (u, v) is:

c_f(u, v) = c(u, v) − f(u, v)         (remaining forward capacity)
c_f(v, u) = f(u, v)                   (capacity available for "undo")

The residual graph G_f has the same vertices as G and contains edge (u, v) whenever c_f(u, v) > 0. Note G_f may contain edges in both directions for a given pair — the forward residual (room to push more) and the backward residual (room to undo prior flow).

An augmenting path is any directed path from s to t in G_f. Its bottleneck is the minimum residual capacity of its edges:

bottleneck(P) = min_{(u,v) ∈ P} c_f(u, v)

Pushing bottleneck(P) units along P (adding to forward edges, subtracting from reverse — equivalently, decrementing forward residuals and incrementing backward residuals) preserves all three flow axioms and increases |f| by exactly bottleneck(P).

3. The Ford-Fulkerson Method (Meta-Algorithm)

ford_fulkerson(G, s, t):
    initialize f(u, v) := 0 for all (u, v)
    while there exists an augmenting path P from s to t in G_f:
        b := bottleneck(P)
        for each (u, v) on P:
            f(u, v) := f(u, v) + b      # push forward
            f(v, u) := f(v, u) − b      # equivalently, increase reverse residual
    return f

Notice what is deliberately unspecified: how we find the augmenting path. The choice matters enormously:

Path-selection rule	Concrete algorithm	Time complexity
Any path (e.g., DFS)	“Naive Ford-Fulkerson”	`O(E ·
Shortest path (BFS)	Edmonds-Karp	O(V · E²)
Blocking flows on level graphs	Dinic’s Algorithm	O(V² · E), or O(E·√V) on unit-capacity
Fattest-path heuristic	Capacity-scaling Ford-Fulkerson	O(E² · log U) where U is max capacity
Push-relabel (different paradigm entirely)	Goldberg-Tarjan	O(V² · √E) or O(V³)

So “Ford-Fulkerson” is best understood as a template for a family of algorithms. When an interviewer says “use Ford-Fulkerson,” they typically mean “use the augmenting-path framework” — the specific path strategy you’ll implement is almost always BFS (Edmonds-Karp) because it’s the simplest with provable polynomial bounds.

4. Tiny Worked Example

Consider this 4-vertex network with source s, sink t, and intermediate vertices a, b. Edge capacities labeled.

        10
    s ─────► a
    │ \      │
    │  \     │ 1
   10│   ─5─►│
    │     \  │
    │      \ ▼      10
    └─────► b ─────► t

Edges with capacities: s→a:10, s→b:10, a→b:1, b→t:10, a→t:5 (let me restate cleanly):

s→a: 10
s→b: 10
a→b:  1
a→t:  5
b→t: 10

Max possible into t is bounded by c(a,t) + c(b,t) = 5 + 10 = 15. Max out of s is c(s,a) + c(s,b) = 20. So the answer is at most 15. Let’s run Ford-Fulkerson.

Iteration 1. Pick some augmenting path; say s → a → t (DFS picks first edge). Bottleneck = min(10, 5) = 5. Push 5.

State after: residuals s→a: 5, a→s: 5, a→t: 0, t→a: 5. Total flow = 5.

Iteration 2. Find another path. s → a → b → t. Bottleneck = min(5, 1, 10) = 1. Push 1.

State: s→a: 4, a→s: 6, a→b: 0, b→a: 1, b→t: 9, t→b: 1. Total flow = 6.

Iteration 3. Find another. s → b → t. Bottleneck = min(10, 9) = 9. Push 9.

State: s→b: 1, b→s: 9, b→t: 0, t→b: 10. Total flow = 15.

Iteration 4. Search residual graph for any s→t path. From s we can reach a (residual 4) and b (residual 1). From a we can reach s (back; useless) and b (forward residual is 0, backward b→a has 1 — wait, a→b has 0, but we’re looking at outgoing edges from a, which include a→t residual 0 and a→b residual 0). From b: b→s (back), b→a (residual 1), b→t (residual 0). The reachable set from s is {s, a, b}; we cannot reach t. No augmenting path → terminate.

Maximum flow = 15. Note the answer matched our naive upper bound c(a,t) + c(b,t). The minimum cut is ({s, a, b}, {t}) with capacity 5 + 10 = 15, foreshadowing the Min-Cut Max-Flow Theorem.

The example also illustrates why the simple “find any path, push, repeat” works: even though our first iteration “wastefully” used a→t capacity (which became a precious resource later), iterations 2 and 3 routed around it, and we still reached the optimum. If the example had been carefully adversarial, we might have needed an undo via the reverse edge — but on this small graph the forward-only flows happened to suffice.

5. Pseudocode (Generic Augmenting Path)

ford_fulkerson(G, s, t):
    for each edge (u, v) in G:
        residual[u][v] := c(u, v)
        residual[v][u] := residual[v][u]    # ensure entry exists; default 0 if not in G
    total_flow := 0
    loop:
        path := find_path(residual, s, t)   # any s→t path of positive-residual edges
        if path is empty:
            break
        b := min residual[u][v] over (u, v) on path
        for each (u, v) on path:
            residual[u][v] := residual[u][v] − b
            residual[v][u] := residual[v][u] + b
        total_flow := total_flow + b
    return total_flow

The inner find_path is the design knob. With DFS (recursive or iterative), this is the textbook Ford-Fulkerson; swap in BFS and you have Edmonds-Karp with much stronger guarantees.

6. Python Implementation

We use an adjacency map of dicts so residual[u][v] gives the current residual capacity from u to v. Reverse edges with initial capacity 0 are pre-added so the residual structure is symmetric.

from collections import defaultdict, deque
 
def build_residual(edges):
    """edges: list of (u, v, capacity). Returns residual graph as dict-of-dicts."""
    residual = defaultdict(lambda: defaultdict(int))
    for u, v, c in edges:
        residual[u][v] += c          # accumulate parallel edges
        residual[v][u] += 0          # ensure reverse entry exists
    return residual
 
def find_path_dfs(residual, s, t):
    """DFS for any augmenting path. Returns list of vertices [s,...,t] or [] if none."""
    parent = {s: None}
    stack = [s]
    while stack:
        u = stack.pop()
        if u == t:
            # reconstruct
            path = []
            while u is not None:
                path.append(u)
                u = parent[u]
            return path[::-1]
        for v, cap in residual[u].items():
            if cap > 0 and v not in parent:
                parent[v] = u
                stack.append(v)
    return []
 
def ford_fulkerson(edges, s, t):
    residual = build_residual(edges)
    total = 0
    while True:
        path = find_path_dfs(residual, s, t)
        if not path:
            return total
        # bottleneck
        b = min(residual[path[i]][path[i+1]] for i in range(len(path)-1))
        # push b along the path
        for i in range(len(path)-1):
            u, v = path[i], path[i+1]
            residual[u][v] -= b
            residual[v][u] += b
        total += b

What’s noteworthy here:

• defaultdict(lambda: defaultdict(int)) lets us write residual[u][v] without pre-declaring keys — convenient for sparse graphs but watch out for accidental key creation during reads (use .get(v, 0) if you don’t want side effects).
• build_residual accumulates parallel edges (more than one u→v edge in input) into a single residual entry, which is correct for max-flow: parallel edges combine.
• find_path_dfs uses an iterative stack; on dense graphs a recursive DFS hits Python’s default recursion limit fast.
• Note that this implementation does not specify the path strategy — it’s literally Ford-Fulkerson. To get Edmonds-Karp, replace the stack with a deque and use popleft() (BFS).

DFS-based Ford-Fulkerson on irrational capacities

A famous pathological example by Zwick (1995, building on Ford-Fulkerson’s own observation) shows a 6-vertex graph with capacities involving (√5 − 1) / 2 (the inverse golden ratio) on which naive DFS-based Ford-Fulkerson never terminates and converges to a flow value strictly less than the true maximum. This is not a numerical artifact — it’s a real combinatorial failure mode. With irrational capacities, only specific path-selection rules (shortest path, fattest path) provably terminate. With integer (or rational) capacities, naive Ford-Fulkerson always terminates, but the run time depends on the maximum flow value |f*| rather than just graph size, which can be exponential in the input bit-length.

7. Complexity

Termination & integrality:

• If all capacities are integers, Ford-Fulkerson terminates in at most |f*| iterations (each iteration increases the flow by at least 1). Total time: O(E · |f*|). This is pseudopolynomial — fast when |f*| is small, terrible when it’s huge (e.g., capacity 10^9 on a tiny graph).
• If capacities are rational, scale to integers; same analysis applies.
• If capacities are irrational, naive Ford-Fulkerson may not terminate at all, and even if it does it may converge to the wrong answer. (Specialized rules — Edmonds-Karp’s BFS, Dinic’s level graphs — are immune.)

Integrality theorem (Ford & Fulkerson, 1956). If all capacities are integers, then there exists an integer-valued maximum flow, and Ford-Fulkerson (with any path strategy) produces one. This is the seed of all “max-flow gives integer matchings” reductions (Bipartite Matching is the canonical example): you reduce to a flow with unit capacities, run any max-flow, and integrality guarantees you get a clean 0/1 selection of edges, no fractional nonsense.

Why O(E · |f*|) per algorithm run:

• Each augmenting iteration finds a path in O(V + E) (DFS or BFS on the residual graph; residual graph has at most 2E edges).
• Each iteration adds at least 1 to the flow (with integer capacities), so at most |f*| iterations.
• Total: O((V+E) · |f*|) = O(E · |f*|) since E ≥ V − 1 for connected graphs.

The dependence on |f*| rather than purely graph size is what makes Edmonds-Karp’s strongly polynomial O(V·E²) so important — it removes that dependence entirely.

8. Variants and Extensions

8.1 Multi-source / multi-sink

If the problem has multiple sources s_1, ..., s_k and/or multiple sinks t_1, ..., t_m (e.g., supplying many factories and many warehouses), introduce a super-source S with edges S → s_i of infinite capacity, and a super-sink T with edges t_j → T of infinite capacity, then run single-source-single-sink max flow on S → T.

8.2 Vertex capacities

The base problem has capacities only on edges. To enforce a capacity c(v) on a vertex (e.g., “this router can process at most 100 packets per second”), split v into two vertices v_in and v_out, route all incoming edges to v_in, all outgoing from v_out, and add an internal edge v_in → v_out with capacity c(v). The vertex bottleneck is now an edge bottleneck.

8.3 Lower bounds on edges

If some edges require at least l(u, v) flow (e.g., contractual minimums), the problem becomes “feasible flow with lower bounds,” reducible to a standard max-flow on a transformed graph. CLRS §26.4 outlines the construction; it’s beyond the typical interview but worth knowing it exists.

8.4 Min-cost max-flow

Each edge has both capacity and cost-per-unit. Find the maximum-value flow whose total cost is minimum among all max-value flows. Solved by repeatedly augmenting along the shortest-cost path (using Bellman-Ford or, after potential adjustment, Dijkstra’s Algorithm). Used in transportation, assignment, and many OR problems.

8.5 Maximum bipartite matching

Reduce to max-flow as described in Bipartite Matching: source → left vertices (cap 1), left → right wherever there’s an edge in the bipartite graph (cap 1), right → sink (cap 1). The integrality theorem ensures the resulting flow corresponds to an actual matching (each left vertex sends at most 1 unit, each right vertex receives at most 1).

8.6 Minimum cut

By the Min-Cut Max-Flow Theorem, computing a maximum flow simultaneously gives a minimum s-t cut: after termination, the set S = {vertices reachable from s in the residual graph} is one side of a min cut.

8.7 Concrete refinements

• Edmonds-Karp — BFS-based, O(V·E²), the one to know cold.
• Dinic’s Algorithm — level graphs + blocking flows, O(V²·E); on unit-capacity graphs, O(E·√V).
• Push-relabel (Goldberg-Tarjan, 1986) — abandons augmenting paths entirely; instead pushes “preflow” greedily and relabels vertex heights. Achieves O(V²·√E) and is what most practical max-flow libraries actually implement.

9. Common Interview Problems

Problem	Pattern
LC 1947 — Maximum Compatibility Score Sum	Reduce to bipartite matching → max flow
LC 1820 — Maximum Number of Accepted Invitations	Bipartite matching (boys ↔ girls)
LC 1349 — Maximum Students Taking Exam	Bipartite matching on grid, or bitmask DP
LC 2172 — Maximum AND Sum of Array	Hungarian / assignment, max-flow-adjacent
”Project Selection” (classic textbook)	Min-cut formulation
”Image Segmentation” (Boykov-Kolmogorov)	Min-cut with foreground/background terminals
”Baseball Elimination”	Max-flow per team to test elimination
”Edge-disjoint paths from s to t”	Max-flow with all unit capacities counts disjoint paths
Network reliability — k-edge-connectivity	Max-flow between vertex pairs

In raw interview frequency, max flow itself is uncommon at the new-grad level — it’s a “senior algo” or “FAANG hard” topic. But the reductions show up surprisingly often disguised as bipartite matching or assignment problems.

10. Pitfalls

10.1 Forgetting reverse edges

Without reverse residuals, you cannot undo flow, and the algorithm will get stuck at suboptimal flows on graphs that need rerouting. The reverse-edge mechanism is the non-trivial part of the algorithm — losing it is the single most common bug.

10.2 Treating the residual graph as the original graph

It is easy to write residual[u][v] -= b for the forward edge and forget residual[v][u] += b for the reverse. Both updates are necessary. Many bugs traced to one-half-of-the-update mistakes.

10.3 Not handling parallel edges / self-loops

Two u → v edges with capacities 3 and 5 should combine into a single residual entry of capacity 8. Self-loops u → u should be discarded (they can never carry flow in a valid s-t flow because they violate flow conservation if u ∉ {s, t}, and they never help even if they could).

10.4 Picking DFS for naive Ford-Fulkerson when capacities are large

The classic textbook example: a graph with edges s→a:M, s→b:M, a→b:1, a→t:M, b→t:M where M = 10^9. If DFS keeps picking the path s→a→b→t (bottleneck 1) followed by s→b→a→t (using the reverse of a→b, bottleneck 1) and so on, you do 2M iterations, each finding a tiny augmenting path. With Edmonds-Karp (BFS), you’d do 2 iterations (s→a→t and s→b→t), each pushing M. Lesson: default to BFS unless you have a reason not to.

10.5 Floating-point capacities

Stick to integer (or rational) capacities. Floating point + augmenting paths is a recipe for non-termination, slightly-wrong answers, and infinite debugging.

10.6 Confusing flow with capacity

f(u, v) is the current flow across edge (u, v); c(u, v) is the limit. Conflating them in code is shockingly common. Use distinct variable names.

10.7 Not setting s ≠ t

If by accident s == t, the answer is “infinite” / undefined. Most implementations return 0 in this degenerate case; check it explicitly when input is user-provided.

10.8 Assuming |f*| matches “what flows out of s” without checking conservation

If a bug breaks flow conservation, the value of the flow can drift — vertices act as silent reservoirs. After any implementation change, run a sanity check that sum_v f(s, v) == sum_u f(u, t) and that for every other vertex, in-flow equals out-flow.

11. Diagram — Augmenting Path and the Residual Graph

flowchart LR
  s((s)) -- "10/10" --> a((a))
  s -- "5/10"  --> b((b))
  a -- "5/5"   --> t((t))
  a -- "1/1"   --> b
  b -- "6/10"  --> t

  subgraph Legend["Edge label = flow / capacity"]
    direction LR
  end

What this diagram shows. Each edge is annotated with flow / capacity. The flow s→a→t carries 5; the flow s→a→b→t carries 1; the flow s→b→t carries 6 directly. Total leaving s = 10 + 5 = 15; total entering t = 5 + 6 + 4 = 15 (the 4 comes from the a→b→t path’s 1 plus the s→b→t direct 6, minus a bookkeeping artifact in this rough drawing — the precise per-edge audit is in §4 above). The residual graph (not drawn separately to avoid clutter) would show, for each flow/capacity pair, a forward residual of capacity − flow and a backward residual of flow. After this flow is in place, no s→t path of strictly positive residual edges remains, certifying optimality.

12. Open Questions

• Does Ford-Fulkerson admit a clean parallel/distributed implementation? (Answer: not in its augmenting-path form; push-relabel parallelizes much better, which is one reason production solvers use it.)
• How do modern max-flow solvers (Boost, LEMON, OR-Tools) decide between Edmonds-Karp, Dinic’s, and push-relabel? (Heuristics on graph density and size; some libraries auto-select.)
• In what sense is max-flow “hard”? Recent breakthroughs (Chen et al. 2022, “Maximum Flow and Minimum-Cost Flow in Almost-Linear Time”) give O(m^{1+o(1)}) algorithms for max-flow on unit-capacity graphs — far beyond interview scope but a stunning theoretical result.

13. See Also

• Edmonds-Karp — Ford-Fulkerson with BFS, O(V·E²)
• Dinic’s Algorithm — level-graph blocking-flow, O(V²·E) and O(E·√V) on unit-capacity
• Min-Cut Max-Flow Theorem — the dual problem and its proof
• Bipartite Matching — canonical max-flow application
• Hopcroft-Karp — specialized bipartite matching, O(E·√V)
• Hungarian Algorithm — weighted bipartite matching
• Breadth-First Search — used inside Edmonds-Karp and Dinic’s
• Depth-First Search — used in Dinic’s blocking-flow phase
• Bellman-Ford — needed for min-cost flow with negative edge costs
• Dijkstra’s Algorithm — alternative path strategy in min-cost flow after potentials
• Big-O Notation
• SWE Interview Preparation MOC