Ford-Fulkerson Method

A flow network is a directed graph $G = (V, E)$ with a source $s$, a sink $t$, and a capacity $c(u,v) \ge 0$ on every edge. A flow is a function $f(u,v)$ satisfying capacity constraints $0 \le f(u,v) \le c(u,v)$ and flow conservation at every vertex other than $s$ and $t$: total flow in equals total flow out. The value of a flow is the net flow leaving $s$, and the maximum flow problem asks for a flow of maximum value. The central construct is the residual graph $G_f$, which depends on the current flow $f$. For every edge $(u,v)$ with capacity $c(u,v)$ and current flow $f(u,v)$, the residual graph contains:

• a forward residual edge $(u,v)$ with residual capacity $c_f(u,v) = c(u,v) - f(u,v)$, present whenever this is positive — it represents unused capacity;
• a backward residual edge $(v,u)$ with residual capacity $c_f(v,u) = f(u,v)$, present whenever this is positive — it represents the ability to cancel flow already sent from $u$ to $v$.

An augmenting path is any directed path from $s$ to $t$ in $G_f$ using only edges of positive residual capacity. Its bottleneck capacity is the minimum residual capacity along the path. Pushing flow equal to the bottleneck along every edge of the path strictly increases the flow value while preserving feasibility — forward edges get more flow, backward edges get flow subtracted (i.e., some previously sent flow is rerouted elsewhere). This is the mechanism that lets Ford-Fulkerson escape locally greedy but globally suboptimal routing decisions made early on.

The method is a loop: build the residual graph, search it for any $s$-$t$ path, augment along it, and repeat. It terminates precisely when the residual graph has no path from $s$ to $t$ — equivalently, when $t$ is unreachable from $s$ using only positive-residual edges. ``` FORD-FULKERSON(G, s, t): for each edge (u, v) in G.E: f(u, v) = 0 f(v, u) = 0 // symmetric bookkeeping, or track only forward while there exists a path p from s to t in the residual graph G_f: c_f(p) = min { c_f(u, v) : (u, v) is an edge on p } // bottleneck for each edge (u, v) on p: if (u, v) is a "forward" original edge: f(u, v) = f(u, v) + c_f(p) else: // (u, v) is a reverse of original edge (v, u) f(v, u) = f(v, u) - c_f(p) // residual capacities are implicitly updated: // c_f(u,v) = c(u,v) - f(u,v), c_f(v,u) = f(u,v) return f ``` ``` EDMONDS-KARP(G, s, t): for each edge (u, v) in G.E: f(u, v) = 0 loop: // BFS in the residual graph, restricted to positive-capacity edges find shortest path p from s to t in G_f using BFS if no such path exists: return f c_f(p) = min { c_f(u, v) : (u, v) on p } for each edge (u, v) on p: augment f along (u, v) by c_f(p) // updates both the forward residual and the paired backward residual ``` Two design choices make this precise and implementable: 1. Residual capacity bookkeeping is usually done with a paired-edge representation: every original edge $(u,v)$ with capacity $c$ is stored alongside a reverse edge $(v,u)$ with capacity $0$ initialized. Sending $\delta$ units of flow along $(u,v)$ decreases the residual capacity of $(u,v)$ by $\delta$ and increases the residual capacity of $(v,u)$ by $\delta$, automatically implementing cancellation. 2. Path search can be any graph search — DFS, BFS, or something smarter. Generic Ford-Fulkerson leaves this unspecified; Edmonds-Karp nails it down to BFS, which finds a shortest (fewest-edges) augmenting path each iteration.

Correctness (why the final flow is maximum). The proof rests on the max-flow min-cut correspondence. Define a cut $(S, T)$ as a partition of $V$ with $s \in S$, $t \in T$; its capacity is the sum of capacities of edges from $S$ to $T$. For any flow $f$ and any cut, the flow value equals the net flow across the cut, which is at most the cut's capacity. So max flow $\le$ min cut always. When Ford-Fulkerson terminates, there is no augmenting path in $G_f$, meaning $t$ is unreachable from $s$ in the residual graph. Let $S$ be the set of vertices reachable from $s$ in $G_f$, and $T = V \setminus S$. Since no residual edge crosses from $S$ to $T$:

• every original edge from $S$ to $T$ must be fully saturated ($f(u,v) = c(u,v)$), otherwise a positive-residual forward edge would exist and $v$ would be reachable;
• every original edge from $T$ to $S$ must carry zero flow ($f(v,u) = 0$), otherwise a positive-residual backward edge would put $v$ in $S$.

The flow value therefore equals exactly the capacity of cut $(S,T)$. Combined with the general inequality (flow value $\le$ any cut capacity), this flow value is the maximum possible, and $(S,T)$ is a minimum cut. This is the constructive core of the Max-Flow Min-Cut Theorem: Ford-Fulkerson doesn't just compute max flow, it exhibits a matching min cut as a certificate of optimality.

Termination and pseudo-polynomial time. Each augmentation strictly increases the flow value by at least 1 (assuming integer capacities), and the flow value is bounded above by the finite min cut capacity, so the loop must terminate. If $f^*$ is the max flow value, at most $f^*$ augmentations occur, each requiring $O(E)$ work to find a path (DFS/BFS) and $O(V)$ to augment, giving $O(E \cdot f^*)$ total time. This is pseudo-polynomial: it depends on the numeric magnitude of capacities, not just the graph size, and can be exponential in the input's bit-length if capacities are large and paths are chosen adversarially.

Non-termination with irrational capacities. If capacities are irrational and augmenting paths are chosen adversarially, Ford-Fulkerson can run forever, converging to a value strictly less than the true max flow — a classical counterexample (due to Ford and Fulkerson themselves, later elaborated) uses the golden ratio to construct an infinite non-terminating sequence of shrinking augmentations. This is why the method, left unspecified, is not an algorithm in the strict sense.

Edmonds-Karp: BFS fixes everything. Edmonds-Karp always augments along a shortest $s$-$t$ path in the residual graph (fewest edges, found by BFS, each edge weight treated as 1). Two facts drive the complexity proof: 1. The shortest-path distance from $s$ to any vertex $v$ in the residual graph is monotonically non-decreasing over the course of the algorithm. Intuitively, augmenting can only remove edges (saturating them) and add reverse edges that point "backward," which cannot shorten future forward paths. 2. Each edge can be the bottleneck (the unique saturating edge) of an augmenting path at most $O(V)$ times. When an edge $(u,v)$ is the bottleneck, it disappears from the residual graph; for it to reappear, flow must be pushed back along $(v,u)$, which requires $v$ to precede $u$ on a later shortest path — and the distance argument shows the shortest-path length to $u$ must have strictly increased by at least 2 between consecutive times $(u,v)$ is a bottleneck. Since shortest-path length is bounded by $V - 1$, this can happen at most $O(V)$ times per edge. With $O(E)$ edges each saturating $O(V)$ times, there are $O(VE)$ augmentations total. Each augmentation costs $O(E)$ for the BFS. Total time:

This bound is independent of capacity values — a genuinely polynomial algorithm, unlike the generic method.

Space. Both variants use $O(V + E)$ space for the graph and residual capacities, plus $O(V)$ for BFS/DFS bookkeeping — no more than the input itself requires.

Honest tradeoffs. Edmonds-Karp's $O(VE^2)$ is often outperformed in practice by other refinements — Dinic's algorithm achieves $O(V^2E)$ using blocking flows and level graphs, and push-relabel variants achieve even better bounds on dense graphs — but Edmonds-Karp remains the simplest provably polynomial instantiation of the Ford-Fulkerson idea and the natural stepping stone toward those algorithms.

Consider this small network (capacities shown), computing max flow from $s$ to $t$:

Run Edmonds-Karp (BFS picks shortest augmenting paths):

Let's be precise about iteration 3. After iterations 1–2, residual capacities are:

• $c_f(s,a) = 10 - 4 = 6$, $c_f(a,s) = 4$
• $c_f(s,b) = 10 - 9 = 1$, $c_f(b,s) = 9$
• $c_f(a,b) = 2$ (untouched), $c_f(b,a) = 0$
• $c_f(a,t) = 4 - 4 = 0$, $c_f(t,a) = 4$
• $c_f(b,t) = 9 - 9 = 0$, $c_f(t,b) = 9$

BFS from $s$: reachable via $s \to a$ (residual 6) and $s \to b$ (residual 1). From $a$, can reach $b$ (residual 2) — but not $t$ (residual 0). From $b$, can reach... nothing new toward $t$ (residual 0). So $t$ is unreachable. The algorithm terminates with flow value $4 + 9 = 13$. Verify optimality via the cut exposed by the final BFS reachable set $S = \{s, a, b\}$, $T = \{t\}$. Capacity of this cut is $c(a,t) + c(b,t) = 4 + 9 = 13$, exactly matching the flow value — confirming, by the max-flow min-cut argument, that 13 is indeed optimal, and no cleverer path selection could have done better. Compare with what a badly chosen DFS-based generic Ford-Fulkerson might do on a network with capacities 1000, 1000, 1 in a specific gadget (the classic pathological example): choosing augmenting paths through the capacity-1 edge repeatedly can force 2000 augmentations of size 1 each, despite the answer being reachable in 2 augmentations of size 1000. This is precisely the failure mode Edmonds-Karp's BFS rule eliminates, since shortest paths never route through unnecessarily long detours when a direct saturating path is available.

The method is named for L. R. Ford Jr. and D. R. Fulkerson, whose 1956 RAND Corporation report on maximum flow in networks — motivated in part by Cold War-era transportation and logistics problems — introduced both the augmenting-path method and the max-flow min-cut theorem it certifies. Their monograph Flows in Networks (1962) became the founding text of network flow theory.

Maximum flow computations underlie network routing and capacity planning in telecommunications, where link bandwidths act as capacities and traffic engineering seeks maximum throughput or robust cut structures. In computer vision, image segmentation via graph cuts (foreground/background separation) is solved as a min-cut/max-flow problem on a pixel-adjacency graph, with Ford-Fulkerson-style augmenting-path solvers (and specialized variants) at the core of tools used in medical imaging and photo editing software.

Bipartite matching — assigning workers to jobs, students to schools, or kidneys to transplant recipients — reduces directly to max flow with unit capacities, foreshadowing Bipartite Matching via Augmenting Paths, where each augmentation corresponds to finding one more compatible match. Airline crew scheduling and transportation logistics, the original motivating domain, still use flow-based formulations for capacity-constrained routing. Compiler and hardware design tools use min-cut computations (the dual output of Ford-Fulkerson) for circuit partitioning, minimizing the wires crossing a boundary. Even project selection and baseball elimination puzzles in combinatorial optimization courses are canonical max-flow reductions taught immediately after this method, building directly on the Max-Flow Min-Cut Theorem this article derives.

Ask the tutor: How does Dinic's algorithm use level graphs and blocking flows to beat Edmonds-Karp's running time?