How max-flow finds the most you can push through a network.

The max-flow problem asks: given a directed graph with edge capacities, what is the most you can push from a source to a sink without exceeding any edge capacity? Lester Ford and Delbert Fulkerson introduced the namesake algorithm in 1956. The dual problem (min-cut) and the algorithmic identity (max-flow = min-cut, Menger 1927) are foundational to combinatorial optimisation.

You have a directed graph (see graph routing for the basic vocabulary). Each edge has a capacity — the maximum amount of "stuff" that can flow along it per unit time. One node is the source; one is the sink. The question: what's the maximum total flow that can move from source to sink, respecting all capacities?

The conservation rule: at every node except source and sink, flow in = flow out. The capacity rule: along every edge, flow ≤ capacity. The answer is a single number.

Repeatedly: find any path from source to sink with remaining capacity; push as much flow as the smallest-capacity edge on that path allows. When no such path exists, you're done — the same termination shape BGP's convergence proofs use.

The trick that makes this work is the residual graph. Every forward edge with flow f and capacity c becomes two edges in residual: forward, capacity c−f; backward, capacity f. The backward edge represents "you can cancel some of the flow you previously sent here". Without it, a greedy algorithm gets stuck in suboptimal saturations and can't recover.

Augmenting along a path that uses a backward edge "undoes" prior flow on that edge while routing flow elsewhere. The total flow goes up; the algorithm makes progress. With this rule, Ford–Fulkerson is provably correct.

Ford–Fulkerson allows any augmenting path. With irrational capacities, this can run forever. With integer capacities it terminates, but with quadratic complexity in the worst case.

Edmonds–Karp picks the shortest path (BFS by edge count). This guarantees O(VE²) — polynomial time on any input. Dinic's algorithm goes further, layering BFS by levels and finding multiple augmenting paths per phase — O(V²E), the standard for serious implementations.

The max-flow min-cut theorem: the maximum flow from s to t equals the minimum total capacity of edges that, if removed, disconnect s from t. This is among the most beautiful duality results in CS — solving max-flow tells you both the flow value and the bottleneck cut.

The cut after the algorithm terminates is the set of edges from "reachable from s in the residual" to "everything else". Useful for: identifying network bottlenecks, proving lower bounds, and image segmentation (foreground/background).

Plenty of problems that don't look like flow problems reduce to one. Bipartite matching (assign tasks to workers, each pair has compatibility) reduces to max-flow with unit capacities. Image segmentation (foreground vs background) is min-cut on a pixel graph. Project selection (pick projects that maximize profit, with prerequisite constraints) reduces to a flow network. Edge-disjoint paths: max-flow with all-unit capacities. The same primitives sit underneath load balancing across multiple paths.

If you can model your problem as a graph with capacities, you can probably solve it with a flow library — and you don't need to understand the algorithm internals. The reduction is the hard part; the algorithm is a black box.

The reductions are why max-flow earns its keep. The bipartite matching problem: you have n tasks on the left and m workers on the right; each task lists which workers can do it. Find the largest set of task-worker pairs such that each task and each worker appears at most once. The naive greedy solution misses the optimum. The flow reduction is exact:

1. Add a source node s with capacity-1 edges to every task.
2. Add a sink node t with capacity-1 edges from every worker.
3. For every (task, compatible-worker) pair, add a capacity-1 edge from task to worker.
4. Run max-flow. The number of saturated edges between tasks and workers is the matching.

The unit capacities ensure each task is matched at most once and each worker accepts at most one task. The reduction takes constant time per edge; running max-flow on the resulting graph (Hopcroft-Karp specialises to bipartite for an O(E√V) bound — better than general max-flow) gives you the matching in time better than any direct algorithm. The same recipe extends to the assignment problem (weighted matching, solved by min-cost max-flow).

Where this ships. Job-board matching algorithms (LinkedIn, Indeed) are essentially weighted bipartite matching at scale. Online ad auctions match ad-slots to advertisers similarly. Hospital residency match (the National Resident Matching Program in the US, ~50,000 medical residents per year) is a classic stable-matching problem, a close cousin. Same algorithmic backbone.

Edmonds-Karp gives O(VE²); good enough for most uses, beatable in theory. The path of progress:

Dinic's algorithm · 1970

O(V²E). Layers BFS into level graphs, finds blocking flows per phase. The default in competitive programming and the backbone of most libraries.

Push-relabel · Goldberg & Tarjan 1988

O(V²√E). Different mental model: maintain "preflow" (excess at nodes) and locally push it toward the sink. Slow theoretical bound; very fast in practice. The algorithm Boost C++ uses.

Orlin's algorithm · 2013

O(VE). The first major improvement on Dinic in decades. Works only for sparse graphs.

Chen, Kyng, Liu, Peng, Probst Gutenberg, Sachdeva · 2022

Almost-linear time: O(E^{1+o(1)}). FOCS 2022 best paper. A theoretical breakthrough — for the first time, max-flow runs in (essentially) the time it takes to read the graph. The algorithm is complex and not yet in production libraries, but the result is foundational.

For most practitioners: use a library (NetworkX, igraph, OR-Tools, LEMON in C++, Boost.Graph). The library implementations use Dinic or push-relabel. The complexity advances after Edmonds-Karp matter for theoretical computer science and for graphs of millions of nodes; below that scale, the asymptotic gain is dominated by constant factors.

Computer vision (image segmentation). Min-cut on a pixel grid graph is the dominant approach to interactive foreground/background separation — "GrabCut" (Microsoft Research, 2004) is implemented in OpenCV's cv2.grabCut. Each pixel becomes a node; edges encode similarity; foreground/background labels seed source/sink. Modern deep-learning approaches have largely replaced this for general segmentation, but min-cut still ships as the refinement step in many pipelines.

Networking (multi-commodity flow). Internet backbone capacity planning runs max-flow variants every day. Cloudflare's traffic engineering allocates flows across hundreds of paths between PoPs to maximise utilisation; Google's B4 SDN uses optimisation that builds on max-flow primitives. The published B4: Experience with a Globally-Deployed Software Defined WAN (SIGCOMM 2013) cites the underlying linear-programming formulation.

Operations research (project selection). The classic example: choose projects with positive NPV subject to prerequisite constraints. Reduce to min-cut, run max-flow, the answer is the cut. McKinsey, BCG, and operations-research consultancies use this in capital-allocation models for clients with tens to hundreds of candidate projects. Software: IBM CPLEX, Gurobi, Google OR-Tools.

Bioinformatics (sequence alignment). Variants of max-flow appear in haplotype phasing, protein-folding pipelines, and metabolic-network analysis. Less famous but consistently present in pharma and academic biology.