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 identity max-flow = min-cut, which generalises Menger's 1927 theorem, 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 is how much total flow can move from source to sink while respecting all capacities.

Two rules constrain the flow. Conservation: at every node except source and sink, flow in equals flow out. Capacity: along every edge, flow is at most the capacity. The result is a single number.

Find any path from source to sink with remaining capacity, and push as much flow as the smallest remaining capacity on that path allows. When no such path exists, the flow is maximal.

The algorithm depends on 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 can get stuck in a suboptimal saturation with no way to recover.

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

Ford–Fulkerson allows any augmenting path. With irrational capacities it may never terminate. With integer capacities it terminates, but the running time is O(E·f), which depends on the value of the maximum flow f.

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

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. It is a classic duality result: solving max-flow gives 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". Min-cuts are used to find network bottlenecks, prove lower bounds and segment images (foreground/background).

Many 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 are max-flow with all-unit capacities. Similar primitives appear in load balancing across multiple paths.

If you can model your problem as a graph with capacities, you can usually solve it with a flow library without knowing the algorithm's internals. The reduction is the hard part.

Reductions are what make max-flow useful. 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 gives the exact optimum:

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 gives the matching. Hopcroft-Karp specialises this case and reaches O(E√V), which is better than the general bound. The same recipe extends to the assignment problem (weighted matching, solved by min-cost max-flow).

Where this is used. Job-board matching is a form of weighted bipartite matching at scale, and online ad auctions match ad slots to advertisers in a similar way. The US hospital residency match (the National Resident Matching Program, ~50,000 medical residents per year) is a stable-matching problem, a close relative.

Edmonds-Karp gives O(VE²), which is good enough for most uses but beatable in theory. The main later algorithms:

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). Works differently: it maintains a "preflow" (excess at nodes) and locally pushes it toward the sink. The theoretical bound is weak but it is fast in practice, and Boost C++ uses it.

Orlin's algorithm · 2013

O(VE). The first major improvement on Dinic in decades.

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

Almost-linear time: O(E^{1+o(1)}). FOCS 2022 best paper. Max-flow now runs in close to the time it takes to read the graph. The algorithm is complex and not yet in production libraries.

For most practitioners: use a library (NetworkX, igraph, OR-Tools, LEMON in C++, Boost.Graph). Library implementations use Dinic or push-relabel. Complexity improvements beyond Edmonds-Karp matter mainly for theory and for graphs with millions of nodes; below that scale, constant factors dominate.

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. Deep-learning approaches have largely replaced this for general segmentation, but min-cut is still the refinement step in some pipelines.

Networking (multi-commodity flow). Backbone capacity planning uses max-flow variants. Cloudflare's traffic engineering allocates flows across many paths between PoPs to maximise utilisation, and 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 it to min-cut, run max-flow, and the cut is the answer. Capital-allocation models with tens to hundreds of candidate projects use this approach. Solvers include IBM CPLEX, Gurobi and Google OR-Tools.

Bioinformatics (sequence alignment). Variants of max-flow appear in haplotype phasing and metabolic-network analysis.