Ford–Fulkerson method

Ford–Fulkerson method
Name	Ford–Fulkerson method
Inventor	L. R. Ford, Jr. and D. R. Fulkerson
Introduced	1956
Complexity	Variable; depends on augmenting path selection
Input	flow network
Output	maximum flow and minimum cut

Ford–Fulkerson method is an algorithmic framework for computing a maximum flow in a capacitated network by iteratively finding augmenting paths and increasing flow until no augmenting path remains. The method connects to foundational results in combinatorial optimization and graph theory, including the Max-flow min-cut theorem, and has influenced algorithms in computer science and operations research such as the Edmonds–Karp algorithm, the Dinic's algorithm, and the Push–relabel algorithm.

Introduction

The Ford–Fulkerson method operates on a directed capacitated graph with a designated source and sink, seeking a feasible flow that maximizes throughput. It relies on concepts like residual capacities, residual graphs, and augmenting paths to iteratively improve a candidate flow. The approach is central to problems arising in Telecommunications, transportation, Operations research, and classical examples such as the Assignment problem, Bipartite matching, and the Circulation problem.

Algorithm

Begin with zero flow on all edges and construct the initial residual graph. Repeatedly find an augmenting path from source to sink in the residual graph (using search strategies such as Depth-first search, Breadth-first search, or priority methods). Increase flow along the path by the minimum residual capacity (bottleneck) and update residual capacities and reverse edges. Continue until no augmenting path exists; the current flow is then maximum by the Max-flow min-cut theorem.

Different path-finding strategies yield specific named algorithms: using Breadth-first search yields the Edmonds–Karp algorithm, selecting shortest augmenting paths by level graphs leads to Dinic's algorithm, and choosing highest admissible pushes corresponds to the Push–relabel algorithm variants. Implementations interact with data structures studied in Algorithm engineering, Priority queue, and Dynamic trees to manage performance for large inputs like those in Internet, Power grid, or Rail transport models.

Complexity and termination

Termination and running time depend on capacities and augmenting path selection. If capacities are integral, the method terminates after a finite number of augmentations, bounded by the value of the maximum flow; this links to results in Integer programming and Total unimodularity. With arbitrary real capacities, naive path choices can cause nontermination or infinite loops; this motivates deterministic strategies like Edmonds–Karp algorithm which guarantees O(V E^2) time, and Dinic's algorithm with O(V^2 E) or O(E sqrt(V)) for unit networks. Further improvements exploit Scaling algorithm techniques, Capacity scaling, and data structures from Sleator–Tarjan link-cut trees to approach near-linear behavior on special classes of graphs like planar networks studied in Graph drawing and Planar graph theory.

Correctness and proof

Correctness follows from the invariant that flow conservation and capacity constraints are maintained at every augmentation, and from termination implying no s–t path in the residual graph. By the Max-flow min-cut theorem first proved by L. R. Ford, Jr. and D. R. Fulkerson and later formalized in many texts such as those by John Hopcroft and Jeffrey Ullman, absence of augmenting paths implies the cut defined by reachable vertices from the source is minimum. Proof techniques connect to Linear programming duality and proofs used in works by D. R. Fulkerson and expositions in textbooks by Michael Garey and David Johnson.

Variants and improvements

Multiple refinements address performance and stability. The Edmonds–Karp algorithm fixes path choice to BFS to bound augmentations. Dinic's algorithm uses level graphs and blocking flows to reduce rounds; Push–relabel algorithm uses preflows and relabel operations to obtain practical speedups and provides strong worst-case guarantees. Capacity scaling and Cost-scaling algorithm techniques integrate with the Minimum-cost flow problem and algorithms by John B. Orlin and Andrew Goldberg. Other enhancements include using Dynamic trees by Sleator and Tarjan and multicore adaptations informed by research at institutions like MIT and Stanford University to handle large-scale networks such as those in Google and Amazon infrastructures.

Applications

The method and its descendants apply to bipartite matching in Kőnig's theorem contexts, Maximum bipartite matching, and scheduling problems in Airlines and Logistics. They model routing in Telecommunications, capacity planning in Power grid and Water distribution, and allocation in Supply chain scenarios at companies like IBM and Microsoft. In theoretical computer science, they underpin algorithms for Image segmentation in Computer vision, Network reliability studies, and combinatorial problems such as Edge-disjoint paths problem and Disjoint paths problem analyzed in conferences like STOC and FOCS.

History and development

Developed by L. R. Ford, Jr. and D. R. Fulkerson in the mid-20th century, the method appeared in a 1956 paper and subsequent monographs that shaped Combinatorial optimization and Operations research. The framework influenced algorithmic developments by Jack Edmonds, Richard Karp, and later refinements by A. V. Aho, John Hopcroft, and Jeffrey Ullman. Over decades, research from institutions such as Bell Labs, Princeton University, and University of California, Berkeley produced analyses leading to modern variants and applications across industry and academia showcased in venues like SIAM and INFORMS meetings.

Category:Graph algorithms