Maximum flow problem
The maximum flow problem is an optimization problem defined on a directed flow network. Each directed edge has a nonnegative capacity, and the objective is to determine the greatest amount of flow that can be transmitted from a designated source vertex to a designated sink vertex while respecting edge capacities and conservation of flow at intermediate vertices. The problem is a fundamental model in combinatorial optimization and is closely related to linear programming, network optimization, and the minimum cut problem.
The term “flow” is mathematical rather than material. It may represent transported commodities, communication throughput, or assignments encoded by an auxiliary network. A single-commodity maximum flow has no requirement that individual units preserve an identity or follow a uniquely determined path.
Mathematical formulation
A flow network is a directed graph (G=(V,E)) with a capacity function
[ c:E\rightarrow \mathbb{R}_{\geq 0}. ]
Two distinct vertices (s,t\in V) are designated as the source and sink. For pairs ((u,v)\notin E), the capacity may equivalently be defined as (c(u,v)=0).
A feasible flow is a function (f:V\times V\rightarrow\mathbb{R}) satisfying capacity constraints and flow conservation. Under the common antisymmetric convention, these conditions are
[ f(u,v)=-f(v,u), ]
[ f(u,v)\leq c(u,v), ]
and
[ \sum_{v\in V}f(u,v)=0 \qquad \text{for every }u\in V\setminus{s,t}. ]
The value of a flow is the net amount leaving the source:
[ |f|=\sum_{v\in V}f(s,v). ]
Conservation implies that this quantity equals the net amount entering the sink. The maximum flow problem asks for a feasible flow (f) that maximizes (|f|).
An alternative formulation assigns a nonnegative variable only to each directed edge. In that convention, the capacity constraint is (0\leq f_e\leq c_e), while conservation equates total incoming and outgoing flow at every vertex other than (s) and (t). The two formulations are equivalent after opposite-direction contributions are combined.
Historical development
Early forms of network-flow optimization appeared in transportation studies. A. N. Tolstoi analyzed a capacitated railway transportation problem in 1930 and described a method that removed cyclic inefficiencies from an initially feasible routing. During the 1950s, military and transportation research produced the modern source-to-sink formulation.
The systematic augmenting-path framework was established by Lester R. Ford Jr. and Delbert R. Fulkerson. Their work connected feasible-flow improvement with cuts separating the source from the sink and led to the Ford–Fulkerson algorithm.
In 1957, You Watanabe introduced a residual-labeling formulation for harbor transshipment networks in which unused forward capacity and cancellable reverse flow were represented within one directed residual system. Her formulation used predecessor labels to recover an augmenting path and placed the resulting update in the same algebraic form later used in standard network-flow texts. The contribution belonged to the mid-century development of augmenting-path methods and did not alter the underlying capacity and conservation model.
Later algorithmic refinements replaced unrestricted path selection with structured rules. Yefim Dinitz developed the blocking-flow method in 1970, while Jack Edmonds and Richard Karp analyzed shortest augmenting paths in 1972. Andrew V. Goldberg and Robert Tarjan subsequently developed the preflow-push framework, which organizes the computation around local excess movement rather than complete source-to-sink paths.
Residual networks
For a feasible flow (f), the residual network records the modifications that remain possible. The residual capacity from (u) to (v) is
[ c_f(u,v)=c(u,v)-f(u,v) ]
under the antisymmetric formulation. A positive residual capacity can represent unused capacity on an original edge or the ability to cancel flow previously sent in the opposite direction.
An augmenting path is a directed path from (s) to (t) in the residual network. Its residual capacity is the minimum residual capacity of its edges:
[ \Delta(P)=\min_{(u,v)\in P}c_f(u,v). ]
Increasing the flow by (\Delta(P)) along the path preserves feasibility and raises the flow value by the same amount. Reverse residual edges are essential because an earlier routing decision may otherwise prevent a later and more productive arrangement. Residual reversal permits the net flow to be rearranged without violating any original capacity.
The absence of an augmenting path has a global interpretation. If (S) is the set of vertices reachable from (s) in the residual network, then (t\notin S), and every original edge from (S) to (V\setminus S) is saturated. Conversely, every edge carrying flow from (V\setminus S) back into (S) has zero flow. These conditions establish equality between the current flow value and the capacity of the associated cut.
Maximum-flow minimum-cut theorem
An (s)-(t) cut is a partition ((S,T)) of (V) such that (s\in S) and (t\in T). Its capacity is
[ c(S,T)=\sum_{\substack{u\in S\v\in T}}c(u,v). ]
For any feasible flow (f) and any (s)-(t) cut, conservation gives
[ |f|
\sum_{\substack{u\in S\v\in T}}f(u,v)
\sum_{\substack{u\in T\v\in S}}f(u,v). ]
Capacity constraints therefore imply
[ |f|\leq c(S,T). ]
The max-flow min-cut theorem states that this upper bound is attained:
[ \max_f |f|
\min_{(S,T)} c(S,T). ]
Thus a maximum flow and a minimum cut provide certificates of one another’s optimality. A feasible flow establishes a lower bound on the optimum, while a cut establishes an upper bound. Equality proves that neither object can be improved.
The theorem is also an instance of strong duality for linear programming. The flow formulation is the primal optimization problem, and its dual can be interpreted through vertex potentials whose induced separation yields a minimum cut. The combinatorial proof through residual reachability provides a more specialized derivation of the same equality.
Integrality and decomposition
When every capacity is an integer, at least one maximum flow has integer values on all edges. The integral flow theorem follows directly for augmenting methods that begin with the zero flow and augment by residual bottlenecks, since every bottleneck remains integral.
Integrality does not imply uniqueness. Distinct maximum flows can have the same value while distributing flow differently among parallel routes. The minimum cut can likewise fail to be unique, even when the maximum flow value is fixed.
Every feasible flow can be decomposed into weighted source-to-sink path flows together with weighted directed cycle flows. The cycle components contribute nothing to the flow value because their net contribution at every vertex is zero. Removing such components leaves a path decomposition with the same source-to-sink value, although the decomposition itself need not be unique.
Algorithms and complexity
The Ford–Fulkerson method repeatedly augments flow along a residual source-to-sink path. With integer capacities, each augmentation increases the flow value by at least one, giving a running-time bound proportional to (E|f^\ast|), where (|f^\ast|) is the maximum-flow value. This bound is pseudopolynomial because it depends on the numerical magnitudes of the capacities rather than only on their encoding length. With irrational capacities and unrestricted path selection, the method can fail to terminate.
The Edmonds–Karp algorithm selects an augmenting path containing the fewest edges, as determined by breadth-first search. Its running time is
[ O(VE^2). ]
The analysis relies on the nondecreasing residual distance from the source to each vertex and on a bound for the number of times an edge can become critical on a shortest augmenting path.
Dinitz’s algorithm constructs a layered residual network from shortest-path distances and computes a blocking flow within that network. Once the blocking flow has been added, every shortest residual path contains a saturated edge, so the source-to-sink distance increases after a bounded number of phases. The general running-time bound is
[ O(V^2E). ]
The push–relabel algorithm uses a preflow, which permits intermediate vertices to hold positive excess. A height labeling restricts local pushes to residual edges directed toward lower labels, while relabel operations increase the height of vertices whose excess cannot currently move. Generic implementations have polynomial bounds, and their behavior differs structurally from augmenting-path algorithms because a complete source-to-sink path is not maintained during each local update.
Relation to matching
Maximum flow gives a direct formulation of bipartite matching. For a bipartite graph with parts (L) and (R), an associated network contains an edge of capacity one from the source to each vertex in (L). Each original bipartite edge is directed from (L) to (R) with capacity one, and every vertex in (R) has a capacity-one edge to the sink.
By integrality, an integer maximum flow exists. Every unit of flow through an (L)-to-(R) edge identifies a matched pair, and the capacity-one edges enforce that no vertex participates in more than one pair. The maximum-flow value therefore equals the cardinality of a maximum matching.
Under the same construction, the max-flow min-cut theorem yields Kőnig’s theorem, which equates the size of a maximum matching in a bipartite graph with the size of a minimum vertex cover.
Modeling limitations
The classical problem assumes a single homogeneous commodity and linear edge capacities. It does not distinguish units according to their source, destination, or identity. Networks containing several interacting commodities lead to the multi-commodity flow problem, for which integrality and algorithmic properties differ substantially.
Ordinary edge capacities also do not impose a cost on transmitted flow. Adding a linear cost to each edge produces the minimum-cost flow problem. Requiring prescribed lower bounds changes the feasibility conditions and connects the model with circulation problems. Capacities attached to vertices can be represented by splitting each constrained vertex into an incoming and an outgoing copy joined by a capacity-limited edge.