Ford–Fulkerson Algorithm
The Ford–Fulkerson algorithm is an iterative augmenting-path method that computes the maximum flow from a source to a sink in a capacitated flow network and establishes the max-flow min-cut theorem.
Ford–Fulkerson algorithm (often termed the Ford–Fulkerson method) is a combinatorial optimization procedure within computation and algorithms that computes the maximum feasible flow from a source vertex s to a sink vertex t in a capacitated directed flow network G = (V, E, c). Published in 1956 by Lester R. Ford Jr. and Delbert R. Fulkerson at the RAND Corporation—motivated by evaluations of railway interdiction capacities—the method starts with zero flow everywhere and repeatedly locates an augmenting path from s to t in the residual network Gf, pushing additional flow along that path until no s–t path remains in Gf.
Within computational complexity theory and polyhedral combinatorics, the termination condition of the Ford–Fulkerson method constructively proves the Max-Flow Min-Cut Theorem: in any flow network, the maximum value of an s–t flow equals the minimum capacity of an s–t cut. When augmenting paths are chosen as shortest unweighted paths via Breadth-First Search, the method specializes to the Edmonds–Karp algorithm (1972) running in strongly polynomial O(|V|·|E|2) time; when level-graph blocking flows are used, it specializes to Dinic's algorithm (1970) running in O(|V|2·|E|) time.
Mathematical Formulation, Residual Networks, and Augmenting Paths
Flow Conservation and Capacity Constraints
Let G = (V, E) be a directed graph equipped with a non-negative edge capacity function c : V × V → ℝ≥0 (where c(u, v) = 0 if (u, v) ∉ E), a source vertex s ∈ V, and a distinct sink vertex t ∈ V. An s–t flow is a real-valued function f : V × V → ℝ satisfying two linear constraint families:
- Capacity Constraint: For all (u, v) ∈ V × V, 0 ≤ f(u, v) ≤ c(u, v).
- Flow Conservation (Kirchhoff's Current Law): For every internal vertex u ∈ V \ {s, t}, total incoming flow equals total outgoing flow:
The value of the flow, denoted |f|, is the net flow leaving the source s (which equals the net flow entering the sink t):
Residual Capacity and Backward Cancellation Edges
Pushing flow solely along forward edges in E can trap a greedy solver in a suboptimal state. Ford and Fulkerson resolved this by defining the residual network Gf = (V, Ef) with residual capacity:
When (u, v) ∈ E carries flow f(u, v) > 0, the forward edge retains capacity c(u, v) − f(u, v) while the backward residual edge (v, u) acquires capacity f(u, v) to cancel (reroute) previously assigned flow. The residual edge set is Ef = {(u, v) : cf(u, v) > 0}. An augmenting path p is a simple s–t path in Gf with bottleneck capacity Δ = min(u, v) ∈ p cf(u, v) > 0; augmenting f along p by Δ increases |f| by Δ.
The Max-Flow Min-Cut Theorem and Integrality Property
Three-Way Equivalence Proof
An s–t cut (S, T) is a partition V = S ∪ T with s ∈ S, t ∈ T, and capacity c(S, T) = ∑u∈S ∑v∈T c(u, v). Summing flow conservation across u ∈ S gives |f| = ∑u∈S ∑v∈T (f(u, v) − f(v, u)) ≤ c(S, T). The Max-Flow Min-Cut Theorem states that three conditions are equivalent: (1) f is a maximum flow; (2) Gf contains no s–t augmenting path; and (3) |f| = c(S, T) for some cut (S, T). Indeed, when Gf has no s–t path, setting S to the set of vertices reachable from s in Gf and T = V \ S ensures every forward edge across (S, T) is saturated (f = c) and every backward edge carries zero flow (f = 0), yielding |f| = c(S, T).
The Integrality Theorem
When all capacities c(u, v) are integers, each augmentation increases |f| by an integer Δ ≥ 1. Thus Ford–Fulkerson terminates in at most |f*| steps and establishes the Integrality Theorem: every integer-capacitated network possesses an integral maximum flow, which implies Menger's theorem, Kőnig's theorem, and Hall's marriage theorem for bipartite matching.
Algorithmic Variants and Complexity Scaling
Arbitrary DFS vs. Edmonds–Karp and Dinic's Algorithm
If augmenting paths are chosen by arbitrary Depth-First Search on integer capacities bounded by U, alternating across a unit-capacity cross-edge can require O(|E|·|f*|) pseudo-polynomial time, and on irrational capacities poorly chosen paths can fail to terminate.
| Maximum-Flow Algorithm | Augmenting Strategy | Worst-Case Time Complexity | Bipartite Matching / Unit Networks |
|---|---|---|---|
| Ford–Fulkerson (DFS, 1956) | Arbitrary path in Gf | O(|E|·|f*|) (pseudo-polynomial) | O(|V|·|E|) |
| Capacity Scaling (Gabow 1985) | Bottleneck threshold Δ = 2k | O(|E|2 log U) | O(|V|·|E|) |
| Edmonds–Karp (BFS, 1972) | Shortest unweighted path in Gf | O(|V|·|E|2) (strongly polynomial) | O(|V|·|E|) |
| Dinic's Algorithm (1970) | BFS level graph + DFS blocking flow | O(|V|2·|E|) | O(√|V| · |E|) (Hopcroft–Karp) |
| Push–Relabel (Goldberg & Tarjan 1988) | Local vertex preflow excess & height | O(|V|2√|E|) | O(√|V| · |E|) |
| Almost-Linear Max-Flow (Chen et al. 2022) | Dynamic interior-point L1 routing | O(|E|1+o(1) log U) | O(|E|1+o(1)) |
Edmonds and Karp (1972) proved that selecting shortest augmenting paths via BFS ensures each edge becomes a critical bottleneck at most |V|/2 times, bounding total augmentations by O(|V|·|E|) and total runtime by O(|V|·|E|2). In minimum-cost flow problems, shortest augmenting paths are found using the Bellman-Ford algorithm or potential-reweighted Dijkstra's algorithm.
Applications in Systems Biology, Genomics, and Computer Vision
In systems biology, max-flow min-cut duality identifies bottleneck choke points and minimal reaction cut sets in metabolic networks alongside flux balance analysis. In transcriptomics, RNA-seq isoform assemblers (StringTie, Traph) order splice graphs via topological sorting and decompose read coverage into mRNA transcripts via minimum-cost network flow, while Picard (1976) showed that finding maximum-weight closed subgraphs in dependency graphs (after collapsing cycles via Tarjan's strongly connected components algorithm) reduces to minimum s–t cut.
Frequently Asked Questions
Why are backward edges with capacity f(u, v) needed in the residual network?
Without backward edges, an early augmenting path that routes flow across a shared middle edge (u, v) can block a later path from reaching the sink. Pushing flow along the backward residual edge (v, u) cancels flow on (u, v) and redirects the two incoming streams onto separate parallel routes to t.
How is the minimum s–t cut extracted once Ford–Fulkerson terminates?
Once no augmenting path remains in Gf, a single BFS or DFS from s along edges with positive residual capacity cf(u, v) > 0 identifies the reachable vertex set S. The partition (S, V \ S) is a minimum-capacity s–t cut.
References
- Ford, L. R., & Fulkerson, D. R. (1956). "Maximal flow through a network." Canadian Journal of Mathematics, 8, 399–404. https://doi.org/10.4153/CJM-1956-045-5
- Dinic, E. A. (1970). "Algorithm for solution of a problem of maximum flow in a network with power estimation." Soviet Mathematics Doklady, 11(5), 1277–1280. https://mathscinet.ams.org/mathscinet-getitem?mr=0287976
- Edmonds, J., & Karp, R. M. (1972). "Theoretical improvements in algorithmic efficiency for network flow problems." Journal of the ACM, 19(2), 248–264. https://doi.org/10.1145/321694.321699
- Goldberg, A. V., & Tarjan, R. E. (1988). "A new approach to the maximum-flow problem." Journal of the ACM, 35(4), 921–940. https://doi.org/10.1145/48014.61051
- Chen, L., Kyng, R., Liu, Y. P., Peng, R., Probst Gutenberg, M., & Sachdeva, S. (2022). "Maximum flow and minimum-cost flow in almost-linear time." Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS), 612–623. https://doi.org/10.1109/FOCS54457.2022.00064