In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate.
The maximum flow problem can be seen as a special case of more complex network flow problems, such as the circulation problem. The maximum value of an s-t flow (i.e., flow from source s to sink t) is equal to the minimum capacity of an s-t cut (i.e., cut severing s from t) in the network, as stated in the max-flow min-cut theorem.
The maximum flow problem was first formulated in 1954 by T. E. Harris and F. S. Ross as a simplified model of Soviet railway traffic flow.[1] [2] [3] In 1955, Lester R. Ford, Jr. and Delbert R. Fulkerson created the first known algorithm, the Ford–Fulkerson algorithm.[4] [5] In their 1955 paper, Ford and Fulkerson wrote that the problem of Harris and Ross is formulated as follows (see p. 5):
Consider a rail network connecting two cities by way of a number of intermediate cities, where each link of the network has a number assigned to it representing its capacity. Assuming a steady state condition, find a maximal flow from one given city to the other.In their book Flows in Network, in 1962, Ford and Fulkerson wrote:
It was posed to the authors in the spring of 1955 by T. E. Harris, who, in conjunction with General F. S. Ross (Ret.), had formulated a simplified model of railway traffic flow, and pinpointed this particular problem as the central one suggested by the model [11].where [11] refers to the 1955 secret report Fundamentals of a Method for Evaluating Rail net Capacities by Harris and Ross (see p. 5).
Over the years, various improved solutions to the maximum flow problem were discovered, notably the shortest augmenting path algorithm of Edmonds and Karp and independently Dinitz; the blocking flow algorithm of Dinitz; the push-relabel algorithm of Goldberg and Tarjan; and the binary blocking flow algorithm of Goldberg and Rao. The algorithms of Sherman[6] and Kelner, Lee, Orecchia and Sidford,[7] [8] respectively, find an approximately optimal maximum flow but only work in undirected graphs.
In 2013 James B. Orlin published a paper describing an
O(|V||E|)
In 2022 Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva published an almost-linear time algorithm running in
O(|E|1+o(1))
First we establish some notation:
N=(V,E)
s,t\inV
N
g
N
(u,v)\inE
guv
g(u,v).
Definition. The capacity of an edge is the maximum amount of flow that can pass through an edge. Formally it is a map
c:E\to\R+.
Definition. A flow is a map
f:E\to\R
fuv\leqcuv
(u,v)\inE.
\forallv\inV\setminus\{s,t\}:
\sum | |
u:(u,v)\inE,fuv>0 |
fuv=
\sum | |
u:(v,u)\inE,fvu>0 |
fvu.
Remark. Flows are skew symmetric:
fuv=-fvu
(u,v)\inE.
Definition. The value of flow is the amount of flow passing from the source to the sink. Formally for a flow
f:E\to\R+
|f|=\sumv: (s,v)fsv=\sumu: (u,t)fut.
Definition. The maximum flow problem is to route as much flow as possible from the source to the sink, in other words find the flow
frm{max}
Note that several maximum flows may exist, and if arbitrary real (or even arbitrary rational) values of flow are permitted (instead of just integers), there is either exactly one maximum flow, or infinitely many, since there are infinitely many linear combinations of the base maximum flows. In other words, if we send
x
u
y>x
u
\Delta\in[0,y-x]
x+\Delta
u
\Delta
x,y
The following table lists algorithms for solving the maximum flow problem.Here,
V
E
U
U
Method | Year | Complexity | Description | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Linear programming | Constraints given by the definition of a legal flow. See the linear program here. | |||||||||||||
Ford–Fulkerson algorithm | 1955 | O(EU) | As long as there is an open path through the residual graph, send the minimum of the residual capacities on that path. | |||||||||||
Edmonds–Karp algorithm | 1970 | O(VE2) | A specialization of Ford–Fulkerson, finding augmenting paths with breadth-first search. | |||||||||||
Dinic's algorithm | 1970 | O(V2E) | In each phase the algorithms builds a layered graph with breadth-first search on the residual graph. The maximum flow in a layered graph can be calculated in O(VE) V-1 O(min\{V2/3,E1/2\}E) | |||||||||||
MKM (Malhotra, Kumar, Maheshwari) algorithm[14] | 1978 | O(V3) | A modification of Dinic's algorithm with a different approach to constructing blocking flows. Refer to the Malhotra|Kumar|Maheshwari|1978}}|original paper. | |||||||||||
Dinic's algorithm with dynamic trees | 1983 | O(VElogV) | The dynamic trees data structure speeds up the maximum flow computation in the layered graph to O(VElogV) | |||||||||||
General push–relabel algorithm | 1986 | O(V2E) | The push relabel algorithm maintains a preflow, i.e. a flow function with the possibility of excess in the vertices. The algorithm runs while there is a vertex with positive excess, i.e. an active vertex in the graph. The push operation increases the flow on a residual edge, and a height function on the vertices controls through which residual edges can flow be pushed. The height function is changed by the relabel operation. The proper definitions of these operations guarantee that the resulting flow function is a maximum flow. | |||||||||||
Push–relabel algorithm with FIFO vertex selection rule | 1988 | O(V3) | Push-relabel algorithm variant which always selects the most recently active vertex, and performs push operations while the excess is positive and there are admissible residual edges from this vertex. | |||||||||||
Push–relabel algorithm with maximum distance vertex selection rule[15] | 1988 | O(V2\sqrt{E}) | Push-relabel algorithm variant which always selects the most distant vertex from s t | |||||||||||
Push-relabel algorithm with dynamic trees[16] | 1988 | O\left(VElog
\right) | The algorithm builds limited size trees on the residual graph regarding to the height function. These trees provide multilevel push operations, i.e. pushing along an entire saturating path instead of a single edge. | |||||||||||
KRT (King, Rao, Tarjan)'s algorithm[17] | 1994 | O\left(VE
V\right) | ||||||||||||
Binary blocking flow algorithm[18] | 1998 | O\left(E ⋅ min\{V2/3,E1/2\} ⋅ log
⋅ logU\right) | ||||||||||||
James B Orlin's + KRT (King, Rao, Tarjan)'s algorithm[19] | 2013 | O(VE) | Orlin's algorithm solves max-flow in O(VE) E\leq
) O(VE) E>V1+\epsilon | |||||||||||
Kathuria-Liu-Sidford algorithm[20] | 2020 | E4/3+o(1)U1/3 | Interior point methods and edge boosting using \ellp \tildeO(E10/7U1/7) | |||||||||||
BLNPSSSW / BLLSSSW algorithm[22] [23] | 2020 | \tildeO((E+V3/2)logU) | Interior point methods and dynamic maintenance of electric flows with expander decompositions. | |||||||||||
Gao-Liu-Peng algorithm[24] | 2021 | \tilde
| Gao, Liu, and Peng's algorithm revolves around dynamically maintaining the augmenting electrical flows at the core of the interior point method based algorithm from [Mądry JACM ‘16]. This entails designing data structures that, in limited settings, return edges with large electric energy in a graph undergoing resistance updates. | |||||||||||
Chen, Kyng, Liu, Peng, Gutenberg and Sachdeva's algorithm[25] | 2022 | O(E1+o(1)logU) E\expO(log7/8EloglogE)logU | Chen, Kyng, Liu, Peng, Gutenberg and Sachdeva's algorithm solves maximum flow and minimum-cost flow in almost linear time by building the flow through a sequence of E1+o(1) Eo(1) |
For additional algorithms, see .
The integral flow theorem states that
If each edge in a flow network has integral capacity, then there exists an integral maximal flow.
The claim is not only that the value of the flow is an integer, which follows directly from the max-flow min-cut theorem, but that the flow on every edge is integral. This is crucial for many combinatorial applications (see below), where the flow across an edge may encode whether the item corresponding to that edge is to be included in the set sought or not.
Given a network
N=(V,E)
S=\{s1,\ldots,sn\}
T=\{t1,\ldots,tm\}
N
S
T
G=(X\cupY,E)
G
N=(X\cupY\cup\{s,t\},E')
E'
G
X
Y
(s,x)\inE'
x\inX
(y,t)\inE'
y\inY
c(e)=1
e\inE'
Then the value of the maximum flow in
N
G
1
G=(V,E)
V
G'=(Vrm{out}\cupVrm{in},E')
G
Vrm{out}=\{vrm{out}\midv\inV\landvhasoutgoingedge(s)\}
Vrm{in}=\{vrm{in}\midv\inV\landvhasincomingedge(s)\}
E'=\{(urm{out},vrm{in})\inVout x Vin\mid(u,v)\inE\}
Then it can be shown that
G'
M
m
G
C
m
n-m
n
G
G'
Assume we have found a matching
M
G'
C
uout,vin
M
(u,v)
C
C
m
C
vrm{out}
G'
M
v
C
v
C
v
C
vrm{in}
G'
v
C
v
C
C
C
To show that the cover
C
n-m
u
(u,v)\inE
v
(v,u)\inE
v
n
n
m
n-m
Let
N=(V,E)
c:V\to\R+,
f
\sumi\infiv\lec(v) \forallv\inV\backslash\{s,t\}.
In other words, the amount of flow passing through a vertex cannot exceed its capacity. To find the maximum flow across
N
N
v\inV
vin
vout
vin
v
vout
v
c(v)
vin
vout
Given a directed graph
G=(V,E)
s
t
s
t
1. The paths must be edge-disjoint. This problem can be transformed to a maximum flow problem by constructing a network
N=(V,E)
G
s
t
N
1
k
k
2. The paths must be independent, i.e., vertex-disjoint (except for
s
t
N=(V,E)
G
1
s
t
3. In addition to the paths being edge-disjoint and/or vertex disjoint, the paths also have a length constraint: we count only paths whose length is exactly
k
k
k
See main article: Closure problem. A closure of a directed graph is a set of vertices C, such that no edges leave C. The closure problem is the task of finding the maximum-weight or minimum-weight closure in a vertex-weighted directed graph. It may be solved in polynomial time using a reduction to the maximum flow problem.
In the baseball elimination problem there are n teams competing in a league. At a specific stage of the league season, wi is the number of wins and ri is the number of games left to play for team i and rij is the number of games left against team j. A team is eliminated if it has no chance to finish the season in the first place. The task of the baseball elimination problem is to determine which teams are eliminated at each point during the season. Schwartz[27] proposed a method which reduces this problem to maximum network flow. In this method a network is created to determine whether team k is eliminated.
Let G = (V, E) be a network with being the source and the sink respectively. One adds a game nodeij – which represents the number of plays between these two teams. We also add a team node for each team and connect each game node with i < j to V, and connects each of them from s by an edge with capacity rij – which represents the number of plays between these two teams. We also add a team node for each team and connect each game node with two team nodes i and j to ensure one of them wins. One does not need to restrict the flow value on these edges. Finally, edges are made from team node i to the sink node t and the capacity of is set to prevent team i from winning more than .Let S be the set of all teams participating in the league and let
r(S-\{k\})=\sumi,j\}\atopi<j}rij
In the airline industry a major problem is the scheduling of the flight crews. The airline scheduling problem can be considered as an application of extended maximum network flow. The input of this problem is a set of flights F which contains the information about where and when each flight departs and arrives. In one version of airline scheduling the goal is to produce a feasible schedule with at most k crews.
To solve this problem one uses a variation of the circulation problem called bounded circulation which is the generalization of network flow problems, with the added constraint of a lower bound on edge flows.
Let G = (V, E) be a network with as the source and the sink nodes. For the source and destination of every flight i, one adds two nodes to V, node si as the source and node di as the destination node of flight i. One also adds the following edges to E:
In the mentioned method, it is claimed and proved that finding a flow value of k in G between s and t is equal to finding a feasible schedule for flight set F with at most k crews.[28]
Another version of airline scheduling is finding the minimum needed crews to perform all the flights. To find an answer to this problem, a bipartite graph is created where each flight has a copy in set A and set B. If the same plane can perform flight j after flight i, is connected to . A matching in induces a schedule for F and obviously maximum bipartite matching in this graph produces an airline schedule with minimum number of crews.[28] As it is mentioned in the Application part of this article, the maximum cardinality bipartite matching is an application of maximum flow problem.
There are some factories that produce goods and some villages where the goods have to be delivered. They are connected by a networks of roads with each road having a capacity for maximum goods that can flow through it. The problem is to find if there is a circulation that satisfies the demand.This problem can be transformed into a maximum-flow problem.
Let G = (V, E) be this new network. There exists a circulation that satisfies the demand if and only if :
=\sumidi
The problem can be extended by adding a lower bound on the flow on some edges.[29]
In their book, Kleinberg and Tardos present an algorithm for segmenting an image.[30] They present an algorithm to find the background and the foreground in an image. More precisely, the algorithm takes a bitmap as an input modelled as follows: ai ≥ 0 is the likelihood that pixel i belongs to the foreground, bi ≥ 0 in the likelihood that pixel i belongs to the background, and pij is the penalty if two adjacent pixels i and j are placed one in the foreground and the other in the background. The goal is to find a partition (A, B) of the set of pixels that maximize the following quantity
q(A,B)=\sumiai+\sumibi-\sum\begin{matrixi,jadjacent\ |A\cap\{i,j\}|=1\end{matrix}}pij
Indeed, for pixels in A (considered as the foreground), we gain ai; for all pixels in B (considered as the background), we gain bi. On the border, between two adjacent pixels i and j, we loose pij. It is equivalent to minimize the quantity
q'(A,B)=\sumibi+\sumiai+\sum\begin{matrixi,jadjacent\ |A\cap\{i,j\}|=1\end{matrix}}pij
because
q(A,B)=\sumiai+\sumibi-q'(A,B).
We now construct the network whose nodes are the pixel, plus a source and a sink, see Figure on the right. We connect the source to pixel i by an edge of weight ai. We connect the pixel i to the sink by an edge of weight bi. We connect pixel i to pixel j with weight pij. Now, it remains to compute a minimum cut in that network (or equivalently a maximum flow). The last figure shows a minimum cut.
1. In the minimum-cost flow problem, each edge (u,v) also has a cost-coefficient auv in addition to its capacity. If the flow through the edge is fuv, then the total cost is auvfuv. It is required to find a flow of a given size d, with the smallest cost. In most variants, the cost-coefficients may be either positive or negative. There are various polynomial-time algorithms for this problem.
2. The maximum-flow problem can be augmented by disjunctive constraints: a negative disjunctive constraint says that a certain pair of edges cannot simultaneously have a nonzero flow; a positive disjunctive constraints says that, in a certain pair of edges, at least one must have a nonzero flow. With negative constraints, the problem becomes strongly NP-hard even for simple networks. With positive constraints, the problem is polynomial if fractional flows are allowed, but may be strongly NP-hard when the flows must be integral.[31]
O(
O(m4/3)