A process cannot be understood by stopping it. Understanding must move withthe �ow of the process, must join it and �ow with it.
— The First Law of Mentat, in Frank Herbert’s Dune (��6�)Contrary to expectation, �ow usually happens not during relaxing moments ofleisure and entertainment, but rather when we are actively involved in a dif�cultenterprise, in a task that stretches our mental and physical abilities. . . . Flow is hardto achieve without effort. Flow is not “wasting time.”— Mihaly Csíkszentmihályi, Flow: The Psychology of Optimal Experience (����)There’s a difference between knowing the path and walking the path.
— Morpheus [Laurence Fishburne], The Matrix (����)��Maximum Flows & Minimum Cuts
In the mids, U. S. Air Force researcher Theodore E. Harris and retired U. S.
Army general Frank S. Ross wrote a classified report studying the rail networkthat linked the Soviet Union to its satellite countries in Eastern Europe. The
network was modeled as a graph withvertices, representing geographic
regions, andedges, representing links between those regions in the rail
network. Each edge was given a weight, representing the rate at which material
could be shipped from one region to the next. Essentially by trial and error, they
determined both the maximum amount of stuff that could be moved from Russia
into Europe, as well as the cheapest way to disrupt the network by removing
links (or in less abstract terms, blowing up train tracks), which they called“the bottleneck”. Their report, which included the drawing of the network in
Figure . , was only declassified in.
I learned this story from Alexander Schrijver’s fascinating survey “On the history of
combinatorial optimization (till)”; the Harris-Ross report was declassified at Schrijver’s
request. Ford and Fulkerson (who we will meet shortly) credit Harris for formulating the�����. M������ F���� & M������ C���

Figure ��.�. Harris and Ross’s map of the Warsaw Pact rail network. (See Image Credits at the end of
the book.)

This one of the first recorded applications of the maximum flow andminimum cut problems. For both problems, the input is a directed graph
G = (V, E) with two special vertices s and t, called the source and target. As inprevious chapters, I will write u v to denote the directed edge from vertex u
to vertex v. Intuitively, the maximum flow problem asks for the maximum rate
at which some resource can be moved from s to t; the minimum cut problem
asks for the minimum damage needed to separate s from t.

��.�

Flows

An (s , t )-flow (or just a flow if the source and target vertices are clear from context) is a function f : E ! R that satisfies the following conservation constraint
at every vertex v except possibly s and t:
XX
f (u v) =f (v w).
uw

In English, the total flow into v is equal to the total flow out of v. To keep thenotation simple, we define f (u v) = 0 if there is no edge u v in the graph.
The value of the flow f , denoted | f |, is the total net flow out of the source
vertex s:
XX| f | :=f (s w)f (u s).
wumaximum-flow problem, although the precise chronology is somewhat muddled; Harris and Ross
thank George Dantzig “for assistance in formulating the problem”.

��8��.�. Cuts

It’s not hard to prove that | f | is also equal to the total net flow into the target
vertex t, as follows. To simplify notation, let @ f (v ) denote the total net flowout of any vertex v:
XX@ f (v) :=f (u v)
f (v w).
uw

The conservation constraint implies that @ f (v) = 0 or every vertex v except s
and t, soX@ f (v) = @ f (s) + @ f (t).
v

On the other hand,
P any flow that leaves one vertex must enter another vertex, so
we must have v @ f (v) = 0. It follows immediately that | f | = @ f (s) = @ f (t).
Now suppose we have another function c : E ! R 0 that assigns a nonnegative capacity c(e) to each edge e. We say that a flow f is feasible (withrespect to c) if 0  f (e)  c(e) for every edge e. Most of the time we consider
only flows that are feasible with respect to some fixed capacity function c. We saythat a flow f saturates edge e if f (e) = c(e), and avoids edge e if f (e) = 0. The
maximum flow problem is to compute a feasible (s, t)-flow in a given directed
graph, with a given capacity function, whose value is as large as possible.
0/5
5/15

10/20
0/15

s

10/10

t

5/10

0/10

5/20
10/10

Figure ��.�. A feasible (s, t)-�ow with value ��. Each edge is labeled with its �ow/capacity.

��.�

Cuts

An (s, t )-cut (or just cut if the source and target vertices are clear from context)
is a partition of the vertices into disjoint subsets S and T —meaning S [ T = V
and S \ T = ?—where s 2 S and t 2 T .
If we have a capacity function c : E ! R 0 , the capacity of a cut is the sumof the capacities of the edges that start in S and end in T :XX
kS, T k :=c(v w).
v2S w2T(Again, if v w is not an edge in the graph, we assume c(v w) = 0.) Notice thatthe definition is asymmetric; edges that start in T and end in S are unimportant.
�����. M������ F���� & M������ C���The minimum cut problem is to compute an (s, t)-cut whose capacity is as
small as possible.
5
15

20
15

s

10
10

S

t

10
20
10

T

Figure ��.�. An (s, t)-cut with capacity ��. Each edge is labeled with its capacity.

Intuitively, the minimum cut is the cheapest way to disrupt all flow from s
to t. Indeed, it is not hard to show the following relationship between flows
and cuts:
Lemma ��.�. Let f be any feasible (s, t)-flow, and let (S, T ) be any (s, t)-cut.
The value of f is at most the capacity of (S, T ). Moreover, | f | = kS, T k if andonly if f saturates every edge from S to T and avoids every edge from T to S.
Proof: Choose your favorite flow f and your favorite cut (S, T ), and then follow
the bouncing inequalities:| f | = @ f (s)X=@ f (v)
v2S

=
=
=



XX
v2S w

XX
v2S w62SXX
v2S w2TXX

v2S w2TXX

v2S w2T= kS, T kf (v w)f (v w)f (v w)[by definition][conservation constraint]
XX
v2S u

XX
v2S u62SXX
v2S u2Tf (u v)[math, definition of @ ]f (u v)[removing edges from S to S]

f (u v)[definition of cut]f (v w)[because f (u v)c(v w)[because f (v w)  c(v w)]

0][by definition]

In the second step, we are just adding zeros, because @ f (v) = 0 for every vertex
v 2 S \ {s}. In the fourth step, we are removing flow values f (x y) where�����.�. The Max�ow-Mincut Theorem

both x and y are in S, because they appear in both sums: positively when v = x
and w = y, and negatively when v = y and u = x.
The first inequalities in this derivation is actually an equality if and only if f
avoids every edge from T to S. Similarly, the second inequality is actually anequality if and only if f saturates every edge from S to T .
ÉThis lemma immediately implies that if | f | = kS, T k, then f must be a
maximum flow, and (S, T ) must be a minimum cut.

��.�The Max�ow-Mincut Theorem

Surprisingly, in every flow network, there is a feasible (s, t)-flow f and an (s, t)cut (S, T ) such that | f | = kS, T k. This is the famous Maxflow-Mincut Theorem,
first proved by Lester Ford (of shortest-path fame) and Delbert Fulkerson in
and independently by Peter Elias, Amiel Feinstein, and Claude Shannon(of information-theory and maze-solving-robot fame) in.
The Maxflow-Mincut Theorem. In every flow network with source s andtarget t, the value of the maximum (s, t)-flow is equal to the capacity of theminimum (s, t)-cut.
Ford and Fulkerson proved this theorem as follows. Fix a graph G, vertices sand t, and a capacity function c : E ! R 0 . The proof will be easier if we assume
that G is reduced, meaning there is at most one edge between any two vertices uand v. In particular, either c(u v) = 0 or c(v u) = 0. This assumption is easy
to enforce: Subdivide each edge u v in G with a new vertex x, replacing u v
with a path u x v, and define c(u x) = c(x v) = c(u v). The modified
graph has the same maximum flow value and minimum cut capacity as theoriginal graph.
7

7

7

10

10

10

Figure ��.�. Enforcing the one-direction assumption.

Let f be an arbitrary feasible (s, t)-flow in G. We define a new capacity
function c f : V ⇥ V ! R, called the residual capacity, as follows:8><c(u v)c f (u v) = f (v u)>:0f (u v)

if u v 2 E
if v u 2 E
otherwise�����. M������ F���� & M������ C���Intuitively, the residual capacity of an edge indicates how much more flow can be
pushed through that edge. Because f 0 and f  c, these residual capacities
are always non-negative. It is possible to have c f (u v) > 0 even if u v is not anedge in the original graph G. Thus, we define the residual graph G f = (V, E f ),where E f is the set of edges whose residual capacity is positive. Most residual
graphs are not reduced; in particular, if 0 < f (u v) < c(u v), then the residual
graph G f contains both u v and its reversal v u.
0/5

5
10

5/15

10/20

s

5
10

0/15
10/10

t

5/10

s

10

10

15

5

t

5
5

0/10

10

5/20

15

10/10

10

Figure ��.�. A �ow f in a weighted graph G and the corresponding residual graph G f .

Now we have two cases to consider: Either there is a directed path from thesource vertex s to the target vertex t in the residual graph G f , or there isn’t.
First suppose the residual graph G f contains a directed path P from s to t; wecall P an augmenting path. Let F = minu v2P c f (u v) denote the maximum
amount of flow that we can push through P. We define a new flow f 0 : E ! R(in the original graph) as follows:8>< f (u v) + F if u v 2 P0
f (u v) = f (u v) F if v u 2 P>: f (u v)
otherwise
5

5/5

10

5
10

s

10

5/15

10/20

10

15

5

t

5

0/15

s

t

0/10

5/10

5

10

15

5/10

10

10/20
10/10

Figure ��.6. An augmenting path with value F = 5 and the resulting augmented �ow f 0 .

I claim that this new flow f 0 is feasible with respect to the original capacities c,meaning f 0 0 and f 0  c everywhere. Consider an edge u v in the originalgraph G. There are three cases to consider.
• If the augmenting path P contains u v, thenf 0 (u v) = f (u v) + F > f (u v)���0��.�. The Max�ow-Mincut Theorem

because f is feasible, andf 0 (u v) = f (u v) + F

by definition of f 0

 f (u v) + c f (u v)= f (u v) + c(u v)

by definition of Ff (u v)by definition of c f= c(u v)Duh.

• If the augmenting path P contains the reversed edge v u, thenf 0 (u v) = f (u v)

F < f (u v)  c(u v),

again because f is feasible, andf 0 (u v) = f (u v)Fby definition of f 0

f (u v)c f (v u)

by definition of F

= f (u v)

f (u v)by definition of c f

=0

Duh.

• Finally, if neither u v nor v u is in the augmenting path, then f 0 (u v) =f (u v), and therefore 0  f 0 (u v)  c(u v), because f is feasible.

So f is indeed feasible.
Finally, only the first edge in the augmenting path leaves s, which implies| f 0 | = | f | + F > | f |. Thus, f 0 is a feasible flow with larger value than f . We
conclude that if there is a path from s to t in the residual graph G f , then f is
not a maximum flow.
On the other hand, suppose the residual graph G f does not contain a directed
path from s to t. Let S be the set of vertices that are reachable from s in G f ,and let T = V \ S. The partition (S, T ) is clearly an (s, t)-cut. For every vertex
u 2 S and v 2 T , we havec f (u v) = (c(u v)f (u v)) + f (v u) = 0.

The feasibility of f implies c(u v) f (u v) 0 and f (v u) 0, so in fact wemust have c(u v) f (u v) = 0 and f (v u) = 0. In other words, our flow fsaturates every edge from S to T and avoids every edge from T to S. Lemma. now implies that | f | = kS, T k, which means f is a maximum flow and (S, T )is a minimum cut.
This completes the proof!

É�����. M������ F���� & M������ C�����.�Ford and Fulkerson’s augmenting-path algorithm

Ford and Fulkerson’s proof of the Maxflow-Mincut Theorem immediately suggests an algorithm to compute maximum flows: Starting with the zero flow,
repeatedly augment the flow along any path from s to t in the residual graph,
until there is no such path.
This algorithm has an important but straightforward corollary:Integrality Theorem. If all capacities in a flow network are integers, thenthere is a maximum flow such that the flow through every edge is an integer.
Proof: We argue by induction that after each iteration of the augmenting path
algorithm, all flow values and all residual capacities are integers.
• Before the first iteration, all flow values are 0 (which is an integer), andall residual capacities are the original capacities, which are integers bydefinition.
• In each later iteration, the induction hypothesis implies that the capacity Fof the augmenting path is an integer, so augmenting changes the flow oneach edge, and therefore the residual capacity of each edge, by an integer.
In particular, each iteration of the augmenting path algorithm increases thevalue of the flow by a positive integer. It follows that the algorithm eventuallyhalts and returns a maximum flow.
É
If every edge capacity is an integer, then conservatively, the Ford-Fulkerson
algorithm halts after at most | f ⇤ | iterations, where f ⇤ is the actual maximum
flow. In each iteration, we can build the residual graph G f and perform awhatever-first-search to find an augmenting path in O(E) time. Thus, in thissetting, the algorithm runs in O(E| f ⇤ |) time in the worst case.
Jack Edmonds and Richard Karp observed that this running time analysis
is essentially tight. Consider the -node network in Figure . , where X issome large integer. The maximum flow in this network is clearly 2X . However,Ford-Fulkerson might alternate between pushing one unit of flow along theaugmenting path s u v t and then pushing one unit of flow along theaugmenting path s v u t, leading to a running time of ⇥(X ) = ⌦(| f ⇤ |).
X

s

v

X

t

1
X

u

X

Figure ��.�. Edmonds and Karp’s bad example for the Ford-Fulkerson algorithm.

�����.�. Ford and Fulkerson’s augmenting-path algorithm

Ford and Fulkerson’s algorithm is usually fast in practice, and it is always fast
when the maximum flow value | f ⇤ | is small, but without further constraints on
the augmenting paths, this is not an efficient algorithm in worst case. Edmonds
and Karp’s bad example network can be described using only O(log X ) bits; thus,
the running time of Ford-Fulkerson is actually exponential in the input size.
™Irrational Capacities

But what if the capacities are not integers? If we multiply all the capacities by
the same (positive) constant, the maximum flow increases everywhere by thesame constant factor. It follows that if all the edge capacities are rational, thenthe Ford-Fulkerson algorithm eventually halts, although still in exponential time(in the number of bits used to described the input).
However, if we allow irrational capacities, the algorithm can actually loop
forever, always finding smaller and smaller augmenting paths. Worse yet, thisinfinite sequence of augmentations may not even converge to the maximum flow,
or even to a significant fraction of the maximum flow! The smallest networkthat exhibits this bad behavior was discovered by Uri Zwick in.
Consider the six-node network shown in Figure . . Six of the nine edges
have somep large integer capacity X , two have capacity 1, 2and one has capacity= ( 5 1)/2 ⇡ 0.618034, chosen so that 1=. To prove that theFord-Fulkerson algorithm can get stuck, we can watch the residual capacities of
the three horizontal edges as the algorithm progresses. (The residual capacitiesof the other six edges will always be at least X 3.)
s
X
1

X

X
1

ϕ

X

X

X

t

A

B

C

Figure ��.8. Uri Zwick’s non-terminating �ow example, and three augmenting paths.

Suppose the Ford-Fulkerson algorithm starts by choosing the central augmenting path, shown at the top of Figure . . The three horizontal edges, in
In, Ford and Fulkerson described a more complex network, withedges, with the same bad behavior.

vertices and�����. M������ F���� & M������ C���order from left to right, now have residual capacities 1, 0, and . Suppose
inductively that the horizontal residual capacities are k 1 , 0, and k for some
non-negative integer k.
. Augment along path B, adding
now k+1 , k , and 0.

k

to the flow; the residual capacities are. Augment along path C, adding
now k+1 , 0, and k .

kto the flow; the residual capacities are. Augment along path B, adding
are now 0, k+1 , and k+2 .

k+1

to the flow; the residual capacities. Augment along path A, adding
are now k+1 , 0, and k+2 .

k+1

to the flow; the residual capacities

It follows by induction that after 4n+1 augmentation steps, the horizontal edges
have residual capacities 2n 2 , 0, and 2n 1 . As the number of augmentations
grows to infinity, the value of the flow converges to
1+2

1
X
i=1

i

=1+

2
1

=4+

p

5 < 7,

even though the maximum flow value is clearly 2X + 1

7.

Practically-minded readers might wonder why anyone should care about
irrational capacities; after all, computers can’t represent anything but (small)
integers or (small dyadic) rationals exactly. Good question! The mathematician’s
answer is that the restriction to integer capacities is literally artificial; it’s anartifact of digital computational hardware (or perhaps the otherwise irrelevantlaws of physics), not an inherent feature of the abstract computational problem.
But a more practical reason is that the behavior of the algorithm with irrational
inputs tells us something about its worst-case behavior in practice with floatingpoint capacities—terrible! Even with very reasonable capacities, a carelessimplementation of Ford-Fulkerson could enter an infinite loop, simply becauseof round-off error, without ever coming close to the correct answer.

��.� Combining and Decomposing Flows
Flows are normally defined as functions on the edges of a graph satisfying certain
constraints at the vertices. However, flows have a second characterization thatis more natural and useful in certain contexts.
Consider an arbitrary graph G with source vertex s and target vertex t. Fix
any two (s, t)-flows f and g and any two real numbers ↵ and , and consider
the function h: E ! R defined by settingh(u v) := ↵ · f (u v) +��6

· g(u v)��.�. Combining and Decomposing Flowsfor every edge u v; we can write this definition more simply as h = ↵ f + g.
Straightforward definition-chasing implies that h is also an (s, t)-flow with value|h| = ↵| f | + |g|. More generally, any linear combination of (s, t)-flows is alsoan (s, t)-flow.
It turns out that any (s, t)-flow can be written as a weighted sum of flows
with a special structure. For any directed path P from s to t, we define acorresponding path flow as follows:8>
if u v 2 P,
<1P(u v) =1 if v u 2 P,>:0otherwise.
Straightforward definition-chasing implies that the function P : E ! R is indeed
an (s, t)-flow with value 1. I am deliberately overloading the variable P to mean
both the path (a sequence of vertices and directed edges) and the unit flow
along that path.
Similarly, for any directed cycle C, we define a corresponding cycle flow by
setting8>
if u v 2 C,
<1C(u v) =>:0

1 if v u 2 C,otherwise.

Again, it is easy to verify that C : E ! R is an (s, t)-flow with value zero.
Our earlier argument implies that any linear combination of path flows andcycle flows is another flow; this weighted sum is called a flow decomposition.
Moreover, every non-negative flow has a flow decomposition with the following
special structure.
Flow Decomposition Theorem. Every non-negative (s, t)-flow f can be written as a positive linear combination of directed (s, t)-paths and directed cycles.
Moreover, a directed edge u v appears in at least one of these paths or cycles
if and only if f (u v) > 0, and the total number of paths and cycles is at mostthe number of edges in the network.
Proof: We prove the theorem by induction on the number of edges carrying
non-zero flow, intuitively by running the Ford-Fulkerson algorithm backward.
As long as at least one edge in the graph carries positive flow, we can find eitheran (s, t)-path or a directed cycle that carries flow. Subtracting as much flow
as possible from that path or cycle empties at least one edge, so the Recursion
Fairy can give us the rest of the decomposition.
To formalize this argument, we first consider the special case of circulations;these are flows with value 0, where flow is conserved at every vertex. Fix an�����. M������ F���� & M������ C���

4
9

4
3

s

5

t

3

6

11
14
15

4
4

4

5
3

5
5
4

6

3

6

5

6

5

6

3

Figure ��.�. Decomposing a circulation into weighted directed cycles.

arbitrary circulation f in an arbitrary flow network, and let # f denote thenumber of edges u v such that f (u v) > 0. We prove that f can be decomposed
into a positive linear combination of at most max{0, # f 1} cycles, by induction
on # f . There are three cases to consider:• If # f = 0, then f is vacuously a linear combination of zero cycles.
• Suppose f (u v) > 0 for a single directed cycle of edges u v. Then # f
and f is trivially a linear combination of one cycle.

2,• Otherwise, pick an arbitrary edge u v with f (u v) > 0. Consider an arbitrary walk v0 v1 v2 · · · with v0 = u and v1 = v, such that f (vi 1 vi ) > 0
for every index i. The conservation constraint implies that every vertex withincoming flow also has outgoing flow, so we can make this walk arbitrarily
long; in particular, the walk must eventually visit some vertex more thanonce. Let k be the smallest index such that v j = vk for some index j < k.
The subwalk v j v j 1 · · · vk is a simple directed cycle C.
Define F := mine2C f (e), and consider the function f 0 := f F · C, ormore verbosely,(f (u v) F if u v 2 C,
f 0 (u v) :=f (u v)otherwise.
Straightforward definition-chasing shows that f 0 is another feasible circulation in G. There is at least one edge e 2 C such that f (e) = F , andtherefore f 0 (e) = 0, which implies # f 0  # f 1. Since fewer edges carryflow in f 0 than in f , the Recursion Fairy can decompose f 0 into at most
# f 0 1  # f 2 cycles. Adding F units of flow around cycle C gives us aflow decomposition for f ; more succinctly: f = f 0 + F · C.
��8��.�. Combining and Decomposing Flows

Now let f be an arbitrary (s, t)-flow in an arbitrary flow network, such that
| f | > 0. Add an edge t s to the network, and define a circulation f 0 by setting
f 0 (t s) = | f | and f 0 (u v) = f (u v) for every original edge u v; observe that
# f 0 = # f + 1 2. The previous argument implies that the circulation f 0 is apositive linear combination of at most # f 0 1 directed cycles. Deleting the edget s gives us a decomposition of the original flow f into at most # f 0 1 = # fpaths and cycles. Specifically, cycles in f 0 that include t s become (s, t)-paths
in f , and cycles in f 0 that do not include t s remain cycles in f .
ÉThe proof of the Flow Decomposition Theorem implies stronger results in
two interesting special cases.
• Any circulation can be decomposed into a weighted sum of cycles; no paths
are necessary.
• Any acyclic (s, t)-flow can be decomposed into a weighted sum of (s, t)-paths;
no cycles are necessary.
Moreover, by canceling flow cycles until no more remain, we can transform any
flow into an acyclic flow with the same value. In particular, every flow network
supports a maximum (s, t)-flow that is acyclic.
The proof also immediately translates directly into an algorithm, similar
to Ford-Fulkerson, to decompose any (s, t)-flow into paths and cycles. The
algorithm repeatedly seeks either a directed (s, t)-path or a directed cycle in theremaining flow, and then subtracts as much flow as possible along that path orcycle, until the flow is empty. We can find a flow path or cycle in O(V ) time asfollows:• If any edge leaving s has positive flow, follow an arbitrary walk from s in theflow graph until it either reaches t (giving us a flow path) or reaches somevertex for the second time (giving us a flow cycle).
• If no edge leaving s has positive flow, find any other vertex v with positive
outflow, and follow an arbitrary walk from v in the flow graph until it reaches
some vertex for the second time (giving us a flow cycle).
In both cases, the conservation constraint implies that this algorithm will neverget stuck. Each iteration takes O(V ) time and removes at least one edge fromthe flow graph; thus, the entire decomposition algorithm runs in O(V E) time.
Flow decompositions provide a natural lower bound on the running time ofany maximum-flow algorithm that builds the flow one path or cycle at a time.
Every flow can be decomposed into at most E paths and cycles, each of which uses
at most V edges, so the overall complexity of the flow decomposition is O(V E).
Moreover, it is easy to construct flows for which every flow decomposition
has complexity ⌦(V E). Thus, any maximum-flow algorithm that explicitly
constructs a flow one path or cycle at a time—in particular, any implementation�����. M������ F���� & M������ C���of Ford and Fulkerson’s augmenting path algorithm—must take ⌦(V E) time in
the worst case.

��.6

Edmonds and Karp’s Algorithms

Ford and Fulkerson’s algorithm does not specify which path in the residual
graph to augment; the poor worst-case behavior of the algorithm can be blamedon poor choices for the augmenting path. In the earlys, Jack Edmonds andRichard Karp published two natural rules for choosing augmenting paths, bothof which led to more efficient algorithms.

Fattest Augmenting Paths
Edmonds and Karp’s first rule is essentially a greedy algorithm:
Choose the augmenting path with largest bottleneck value.
It’s not hard to show that the maximum-bottleneck (s, t)-path in a directed graphcan be computed in O(E log V ) time using a “best-first” traversal, similar to
Jarník’s minimum-spanning-tree algorithm or Dijkstra’s shortest-path algorithm.
The algorithm grows a directed tree T , rooted at s, one vertex at a time, by
repeatedly adding the highest-capacity edge leaving T to T , until T contains
a path from s to t. Alternately, one could emulate Kruskal’s algorithm—insert
edges one at a time in decreasing capacity order until there is a path from s
to t—although this approach is less efficient, at least when the graph is directed.
To complete the running-time analysis of the flow algorithm, we need an
upper bound on the number of iterations before the algorithm halts. In fact,
for arbitrary real capacities, the algorithm may never halt; see Exercise . For
integer capacities, however, we can bound the number of iterations as a functionof the maximum flow value | f ⇤ |, as follows.
Let f be any flow in G, and let f 0 be the maximum flow in the current
residual graph G f . (At the beginning of the algorithm, G f = G and f 0 = f ⇤ .)We have already proved that f 0 can be decomposed into at most E paths andcycles. A simple averaging argument implies that at least one of the paths in thisdecomposition must carry at least | f 0 |/E units of flow. It follows immediatelythat the fattest (s, t)-path in G f carries at least | f 0 |/E units of flow.
Thus, augmenting f along the maximum-bottleneck path in G f multiplies
the value of the remaining maximum flow in G f by a factor of at most 1 1/E.
In other words, the residual maximum flow value decays exponentially with thenumber of iterations. After E · ln| f ⇤ | iterations, the maximum flow value in G f
is at most⇤⇤| f ⇤ | · (1 1/E) E·ln| f | < | f ⇤ | e ln| f | = 1.
�����.6. Edmonds and Karp’s Algorithms(That’s Euler’s constant e, not the edge e. Sorry.) In particular, after E · ln| f ⇤ |iterations, the residual maximum flow value is less than 1. If all capacities areintegers, the residual maximum flow value is also an integer, so it must be 0; inother words, f is a maximum flow!
We conclude that for graphs with integer capacities, the Edmonds-Karp“fattest path” algorithm runs in O(E 2 log E log| f ⇤ |) time. Unlike the worst-caserunning time of raw Ford-Fulkerson, this time bound is actually a polynomial
function of the input size.
Just like the original Ford-Fulkerson algorithm, the "fattest path" algorithm
can get stuck in an infinite loop in networks with arbitrary real capacities.
However, our analysis implies that even if the algorithm never halts, it maintains
a flow f that approaches a maximum flow in the limit.

Shortest Augmenting Paths
The second Edmonds-Karp rule was actually proposed as a practical heuristic
by Ford and Fulkerson in their original maximum-flow paper; a variant of thisrule was independently proposed inby the Russian mathematician Yefim
Dinitz.
Choose the augmenting path with the smallest number of edges.
The shortest augmenting path can be found in O(E) time by running breadth-firstsearch in the residual graph. Surprisingly, the resulting algorithm halts after apolynomial number of iterations, independent of the actual edge capacities!
The proof of this polynomial upper bound relies on two observations
about the evolution of the residual graph. Let f i be the current flow after iaugmentation steps, let Gi be the corresponding residual graph. In particular, f0
is zero everywhere and G0 = G. For each vertex v, let leveli (v ) denote theunweighted shortest-path distance from s to v in Gi , or equivalently, the levelof v in a breadth-first search tree of Gi rooted at s. In particular, if there is nopath from s to v in Gi , then leveli (v) = 1 (because min ? = 1).
Our first observation is that the level of a vertex can only increase over time.
Lemma ��.�. leveli (v)leveli 1 (v) for all vertices v and all integers i > 0.

Proof: Fix an arbitrary positive integer i > 0 and an arbitrary vertex v. We
prove the claim by induction on leveli (v) (and not on the integer i). As an
inductive hypothesis, assume for every vertex u such that leveli (u) < leveli (v),that leveli (u) leveli 1 (u). There are three cases to consider.
Specifically, Dinitz discovered a more complex maximum-flow algorithm, while he wasa student in an algorithms class taught by Georgy Adelson-Velsky (the “AV” in AVL trees), in
response to an in-class exercise. Dinitz’s algorithm also pushes flows along shortest paths, butwith additional bookkeeping to reduce the running time from O(V E 2 ) to O(V 2 E).

�����. M������ F���� & M������ C���• If v = s, we immediately have leveli (s) = leveli 1 (s) = 0.
• If there is no path from s to v in Gi , then leveli (v) = 1

leveli 1 (v).

• Otherwise, let s · · · u v be any unweighted shortest path from s to v in
the graph Gi . Because this is a shortest path, we have leveli (v) = leveli (u)+1,
so the inductive hypothesis implies leveli (u) leveli 1 (u). To complete theproof, we need to show that leveli 1 (u)leveli 1 (v) 1. We have two
subcases to consider.
– If u v is an edge in Gi 1 , then leveli 1 (v)  leveli 1 (u) + 1, because thelevels are defined by breadth-first traversal.
– On the other hand, if u v is not an edge in Gi 1 , then its reversal
v u must be an edge in the ith augmenting path, which by definitionis the shortest path from s to t in Gi 1 . It follows that leveli 1 (v) =leveli 1 (u) 1  leveli 1 (u) + 1.

In both subcases, we conclude that leveli (v) = leveli (u)+1leveli 1 (v).

leveli 1 (u) + 1

ÉWhenever we augment the flow, the bottleneck edge in the augmenting
path disappears from the residual graph, and some edges in the reversal of theaugmenting path may (re-)appear. Our second observation is that an edge
cannot appear or disappear too many times.
Lemma ��.�. During the execution of the Edmonds-Karp shortest-augmentingpath algorithm, each edge u v disappears from the residual graph G f at mostV /2 times.
Proof: Suppose u v is in two residual graphs Gi and G j+1 , but not in any of
the intermediate residual graphs Gi+1 , . . . , G j , for some i < j. Then u v must
be in the ith augmenting path, so leveli (v) = leveli (u) + 1, and v u must beon the jth augmenting path, so level j (v) = level j (u) 1. The previous lemma
implies thatlevel j (u) = level j (v) + 1

leveli (v) + 1 = leveli (u) + 2.

In other words, between the disappearance and reappearance of u v, thedistance from s to u increased by at least 2. Because every level is either lessthan V or infinite, the number of disappearances is at most V /2.
É
Now we can derive an upper bound on the number of iterations. Because eachedge disappears at most V /2 times, there are at most EV /2 edge disappearances
overall. But at least one edge disappears on each iteration, so the algorithm
must halt after at most EV /2 iterations. Finally, each iteration requires O(E)time, so the overall algorithm runs in O(V E 2 ) time.
�����.�. Further Progress

��.�

Further ProgressThis is nowhere near the end of the story for maximum-flow algorithms. Decadesof further research have led to several faster algorithms, some of which aresummarized in Figure . . All the listed algorithms listed compute a
maximum flow in several iterations. Most of these algorithms have two variants:
a simpler version that performs each iteration by brute force, and a fastervariant that uses sophisticated data structures to maintain a spanning tree ofthe flow network, so that each iteration can be performed (and the spanning
tree updated) in logarithmic time. There is no reason to believe that the bestalgorithms known so far are optimal; indeed, maximum flows are still a very
active area of research.
Technique

DirectWith dynamic trees

Source(s)Blocking �ow

2O(V E)O(V E log V )[Dinitz; Karzanov; Even and Itai;
Sleator and Tarjan]

Network simplex

O(V 2 E)O(V E log V )[Dantzig; Goldfarb and Hao;
Goldberg, Grigoriadis, and Tarjan]

Push-relabel (generic)O(V 2 E)—O(V 3 )O(V E log(V 2 /E))p
Push-relabel (highest label) O(V 2 E) —Push-relabel (FIFO)[Goldberg and Tarjan][Goldberg and Tarjan][Cheriyan and Maheshwari; Tunçel]

Push-relabel-add games—

O(V E log E/(V log V ) V ) [Cheriyan and Hagerup;

Pseudo�ow

O(V 2 E)O(V E log V )[Hochbaum]

Pseudo�ow (highest label)O(V 3 )O(V E log(V 2 /E))

[Hochbaum and Orlin]

2

King, Rao, and Tarjan]

Incremental BFSO(V E)O(V E log(V 2 /E))

[Goldberg, Held, Kaplan, Tarjan,
and Werneck]

Compact networks—

O(V E)[Orlin]Figure ��.��. Several purely combinatorial maximum-�ow algorithms and their running times.

The fastest known (purely combinatorial) maximum-flow algorithm, announced by James Orlin in, runs in O(V E) time, exactly matching theworst-case complexity of a flow decomposition. The details of Orlin’s algorithm
are far beyond the scope of this book; in addition to his own new techniques,
Orlin uses several older algorithms and data structures as black boxes, most ofwhich are themselves quite complicated. In particular, Orlin’s algorithm does
not construct an explicit flow decomposition; in fact, for graphs with only O(V )edges, an extension of his algorithm actually runs in only O(V 2 / log V ) time!
Nevertheless, for purposes of analyzing algorithms that use maximum flows,
To keep this table short, I have deliberately omitted algorithms whose running time depends
on edge capacities or the maximum flow value. Even with this restriction, the list is embarrassingly
incomplete!

�����. M������ F���� & M������ C���this is the time bound you should cite. So write the following sentence on yourcheat sheets and cite it in your homeworks:
Maximum flows can be computed in O(V E) time.
Finally, faster maximum-flow algorithms are known for unit-capacity networks, where every edge has capacity 1. In, Alexander Karzanov provedthat Dinitz’s blocking-flow algorithm—the first algorithm listed in the table
above—runs in O(min{V 2/3 , E 1/2 } E) time in this setting. (This time boundappears to break the ⌦(V E) flow decomposition barrier, but in fact Karzanov’s
analysis implies that any flow in a unit-capacity network can be decomposed
into paths with total complexity O(min{V 2/3 , E 1/2 } E).) This was the fastest
algorithm known in this setting for four decades. Karzanov’s record was finallybroken in, when Aleksander M dry announced a truly remarkable algorithm
that computes maximum flows in unit-capacity networks in O(E 10/7 polylog E)
time. Again, the details of M dry’s algorithm are far beyond the scope of thisbook, or indeed the expertise of its author.

Exercises. Suppose you are given a directed graph G = (V, E), two vertices s and t,
a capacity function c : E ! R+ , and a second function f : E ! R. Describe
an algorithm to determine whether f is a maximum (s, t)-flow in G.
. Let f and f 0 be two feasible (s, t)-flows in a flow network G, such that
| f 0 | > | f |. Prove that there is a feasible (s, t)-flow with value | f 0 | | f | in theresidual network G f .
. Let u v be an arbitrary edge in an arbitrary flow network G. Prove that if
there is a minimum (s, t)-cut (S, T ) such that u 2 S and v 2 T , then there isno minimum cut (S 0 , T 0 ) such that u 2 T 0 and v 2 S 0 .
. Let (S, T ) and (S 0 , T 0 ) be minimum (s, t)-cuts in some flow network G. Provethat (S \ S 0 , T [ T 0 ) and (S [ S 0 , T \ T 0 ) are also minimum (s, t)-cuts in G.
. Let G be a flow network that contains an opposing pair of edges u v andv u, both with positive capacity. Let G 0 be the flow network obtained from G
by decreasing the capacities of both of these edges by min{c(u v), c(v u)}.
In other words:• If c(u v) > c(v u), change the capacity of u v to c(u v)and delete v u.
���c(v u)

Exercises• If c(u v) < c(v u), change the capacity of v u to c(v u)and delete u v.

c(u v)• Finally, if c(u v) = c(v u), delete both u v and v u.
7

3

10
5
5

Figure ��.��. Enforcing the one-direction assumption.

(a) Prove that every maximum (s, t)-flow in G 0 is also a maximum (s, t)-flowin G. (Thus, by simplifying every opposing pair of edges in G, we obtaina new reduced flow network with the same maximum flow value as G.)(b) Prove that every minimum (s, t)-cut in G is also a minimum (s, t)-cut
in G 0 and vice versa.
(c) Prove that there is at least one maximum (s, t)-flow in G that is not a
maximum (s, t)-flow in G 0 .
. (a) Describe an efficient algorithm to determine whether a given flow
network contains a unique maximum (s, t)-flow.
(b) Describe an efficient algorithm to determine whether a given flow
network contains a unique minimum (s, t)-cut.
(c) Describe a flow network that contains a unique maximum (s, t)-flow but
does not contain a unique minimum (s, t)-cut.
(d) Describe a flow network that contains a unique minimum (s, t)-cut but
does not contain a unique maximum (s, t)-flow.
. An (s, t)-flow in a network G is acyclic if there are no directed cycles where
every edge has a positive flow value; that is, the subgraph of edges withpositive flow value is a dag.
(a) Describe and analyze an algorithm to compute an acyclic maximum(s, t)-flow in a given flow network. Your algorithm should have the same
asymptotic running time as Ford-Fulkerson.
(b) Describe and analyze an algorithm to determine whether every maximum(s, t)-flow in a given flow network is acyclic.
. Let G = (V, E) be a flow network in which every edge has capacity 1 andthe shortest-path distance from s to t is at least d.
�����. M������ F���� & M������ C���(a) Prove that the value of the maximum (s, t)-flow is at most E/d.
(b) Now suppose that G is simple, meaning that for all vertices u and v, there
is at most one edge from u to v. (Flow networks can have parallel edges.)
Prove that the value of the maximum (s, t)-flow is at most O(V 2 /d 2 ).
[Hint: How many nodes are in the average level of a BFS tree rooted
at s?]. Suppose we are given a flow network G = (V, E) in which every edge has
capacity 1, together with an integer k. Describe and analyze an algorithm
to identify k edges in G such that after deleting those k edges, the value ofthe maximum (s, t)-flow in the remaining graph is as small as possible.
. The analysis in our proof of the Flow Decomposition Theorem can betightened. Let G = (V, E) be an arbitrary flow network, and let f be an
arbitrary (s, t)-flow in G.
(a) Prove that if | f | = 0, then f is the weighted sum of at most E V + 1
directed cycles, where f (e) > 0 for every edge e in each of these cycles.
(b) Prove that if | f | > 0, then f is the weighted sum of at most E V + 2
directed paths and directed cycles, where f (e) > 0 for every edge e ineach of these paths and cycles.
(c) Prove that both of the previous upper bounds are tight: There are graphs
in which some circulations cannot be decomposed into less than E V +1
cycles, and some flows cannot be decomposed into less than E V + 2
paths and cycles. [Hint: This is easy.]®

. Our observation that any linear combination of (s, t)-flows is itself an (s, t)flow implies that the set of all (not necessarily feasible) (s, t)-flows in any
graph actually define a real vector space, which we can call the flow space ofthe graph.
(a) Prove that the flow space of any connected graph G = (V, E) has dimension E V + 2.
(b) Let T be any spanning tree of G. Prove that the following collection ofpaths and cycles define a basis for the flow space:• The unique path in T from s to t;• The unique cycle in T [ {e}, for every edge e 62 T .

(c) Let T be any spanning tree of G, and let F be the forest obtained bydeleting any single edge in T . Prove that the following collection ofpaths and cycles define a basis for the flow space:• The unique path in F [ {e} from s to t, for every edge e 62 F that has
one endpoint in each component of F ;��6

Exercises• The unique cycle in F [ {e}, for every edge e 62 F with both endpoints
in the same component of F .
(d) Prove or disprove the following claim: Every connected flow network
has a flow basis that consists entirely of simple paths from s to t.
. Cuts are sometimes defined as subsets of the edges of the graph, instead ofas partitions of its vertices. In this problem, you will prove that these two
definitions are almost equivalent.
We say that a subset X of (directed) edges separates s and t if every
directed path from s to t contains at least one (directed) edge in X . For any
subset S of vertices, let S denote the set of directed edges leaving S; that is,
S := {u v | u 2 S, v 62 S}.

(a) Prove that if (S, T ) is an (s, t)-cut, then S separates s and t.

(b) Let X be an arbitrary subset of edges that separates s and t. Prove that
there is an (s, t)-cut (S, T ) such that S ✓ X .

(c) Let X be a minimal subset of edges that separates s and t. (Such a setof edges is sometimes called a bond.) Prove that there is an (s, t)-cut(S, T ) such that S = X .

. Suppose instead of capacities, we consider networks where each edge u v
has a non-negative demand d(u v). Now an (s, t)-flow f is feasible if andonly if f (u v) d(u v) for every edge u v. (Feasible flow values can now
be arbitrarily large.) A natural problem in this setting is to find a feasible(s, t)-flow of minimum value.
(a) Describe an efficient algorithm to compute a feasible (s, t)-flow, given
the graph, the demand function, and the vertices s and t as input. [Hint:
Find a flow that is non-zero everywhere, and then scale it up to make it
feasible.](b) Suppose you have access to a subroutine M F
that computes
maximum flows in networks with edge capacities. Describe an efficientalgorithm to compute a minimum flow in a given network with edge
demands; your algorithm should call M F
exactly once.
(c) State and prove an analogue of the max-flow min-cut theorem for thissetting. (Do minimum flows correspond to maximum cuts?). For any flow network G and any vertices u and v, let bottleneckG (u, v) denotethe maximum, over all paths ⇡ in G from u to v, of the minimum-capacityedge along ⇡.
�����. M������ F���� & M������ C���(a) Describe and analyze an algorithm to compute bottleneckG (s, t) inO(E log V ) time. This is the amount of flow that the Edmonds-Karpfattest-augmenting-paths algorithm pushes in the first iteration.
(b) Now suppose the flow network G is undirected; equivalently, supposec(u v) = c(v u) for every pair of vertices u and v. Describe and analyze
an algorithm to compute bottleneckG (s, t) in O(V + E) time. [Hint: Find
the median edge capacity.] Why doesn’t this speedup work for directed
graphs?
™

(c) Again, suppose the flow network G is undirected. Describe and analyze an algorithm to construct a spanning tree T of G such thatbottleneck T (u, v) = bottleneckG (u, v) for all vertices u and v. (Edges in T
inherit their capacities from G.) For full credit, your algorithm should
run in O(E) time.

. Suppose you are given a flow network G with integer edge capacities andan integer maximum flow f ⇤ in G. Describe algorithms for the following
operations:(a) I(e): Increase the capacity of edge e by 1 and update themaximum flow.
(b) D(e): Decrease the capacity of edge e by 1 and update themaximum flow.
Both algorithms should modify f ⇤ so that it is still a maximum flow, more
quickly than recomputing a maximum flow from scratch.
. Let G be a network with integer edge capacities. An edge in G is upperbinding if increasing its capacity by 1 also increases the value of the maximum
flow in G. Similarly, an edge is lower-binding if decreasing its capacity by 1
also decreases the value of the maximum flow in G.
(a) Does every network G have at least one upper-binding edge? Prove youranswer is correct.
(b) Does every network G have at least one lower-binding edge? Prove youranswer is correct.
(c) Describe an algorithm to find all upper-binding edges in G, given both G
and a maximum flow in G as input, in O(E) time.
(d) Describe an algorithm to find all lower-binding edges in G, given both G
and a maximum flow in G as input, in O(EV ) time.
. A given flow network G may have more than one minimum (s, t)-cut. Let’s
define the best minimum (s, t)-cut to be any minimum cut (S, T ) with thesmallest number of edges crossing from S to T .
��8Exercises(a) Describe an efficient algorithm to find the best minimum (s, t)-cut when
the capacities are integers.
(b) Describe an efficient algorithm to find the best minimum (s, t)-cut forarbitrary edge capacities.
(c) Describe an efficient algorithm to determine whether a given flow
network contains a unique best minimum (s, t)-cut.
. A new assistant professor, teaching maximum flows for the first time, suggests
the following greedy modification to the generic Ford-Fulkerson augmenting
path algorithm. Instead of maintaining a residual graph, just reduce thecapacity of edges along the augmenting path! In particular, whenever wesaturate an edge, just remove it from the graph. Who needs all that residual
graph nonsense?
GF(G, c, s, t):for every edge e in G
f (e) 0while there is a path from s to t⇡
an arbitrary path from s to tFminimum capacity of any edge in ⇡for every edge e in ⇡f (e)f (e) + F
if c(e) = F
remove e from G
else
c(e)
c(e) F
return f(a) Show that G

Fdoes not always compute a maximum flow.

(b) Show that G
F
is not even guaranteed to compute a good
approximation to the maximum flow. That is, for any constant ↵ > 1,
there is a flow network G such that the value of the maximum flow ismore than ↵ times the value of the flow computed by GF.
[Hint: Assume that GFchooses the worst possible path ⇡ ateach iteration.]. In
Maurice Queyranne published an example of a flow network, shown
below, where Edmonds and Karp’s “fattest path” heuristic does not halt. As
in Zwick’s bad example forp the original Ford-Fulkerson algorithm, denotes
the inverse golden ratio ( 5 1)/2. The three vertical edges play essentiallythe same role as the horizontal edges in Zwick’s example.
The adverb just is almost always subconscious shorthand for “I’m too lazy to figure out thedetails, but you should believe me anyway”, or more succinctly, “This is probably wrong.” Seealso merely, simply, clearly, and obviously.

�����. M������ F���� & M������ C���s(ϕ+1)/2

a

1/2

b

ϕ/2

c

(ϕ+1)/2

d

ϕ/2

1/2

ϕ

ϕ/2

ϕ

(ϕ+1)/21

1/2(ϕ+1)/2eϕ/2f(ϕ+1)/2

g

1/2

h

ϕ/2

t

Figure ��.��. Queyranne’s network, and a sequence of “fattest path” augmentations.

(a) Show that the following infinite sequence of path augmentations is avalid execution of the Edmonds-Karp “fattest path” algorithm. (See thebottom of Figure . .)
Q

for i

F P
:
1 to 1
push 3i 2 units of flow along s a f g b h c d t
push 3i 1 units of flow along s f a b g h c t
push 3i units of flow along s e f a g b c h t(b) Describe a sequence of O(1) path augmentations that yields a maximum
flow in Queyranne’s network.
™

. An (s , t )-series-parallel graph is a directed acyclic graph with two distinguished vertices s and t and with one of the following structures:• Base case: A single directed edge from s to t.
• Series: The union of an (s, u)-series-parallel graph and a (u, t)-seriesparallel graph that share a common vertex u but no other vertices oredges.
• Parallel: The union of two smaller (s, t)-series-parallel graphs withthe same source s and target t, but with no other vertices or edges incommon.
Every (s, t)-series-parallel graph G can be represented by a decomposition
tree, which is a binary tree with three types of nodes: leaves (whichcorresponding to edges in G), series nodes (which correspond to vertices
other than s and t), and parallel nodes. The same series-parallel graphcould be represented by many different decomposition trees.
(a) Suppose you are given a directed graph G with two special vertices s and t.
Describe and analyze an algorithm that either builds a decomposition
tree for G or correctly reports that G is not (s, t)-series-parallel. [Hint:
Build the tree from the bottom up.]���

Exercises

l
g
a

b

e

f

i
h

s

e
c

d

l
j

k

t

a

d
f

b

c

j
i

g

k

h

Figure ��.��. A series-parallel graph and a corresponding decomposition tree. Squares in the decomposition tree are leaves; diamonds are parallel nodes.

(b) Describe and analyze an algorithm to compute a maximum (s, t)-flow ina given (s, t)-series-parallel flow network with arbitrary edge capacities.
[Hint: In light of part (a), you can assume that you are actually given
the decomposition tree. First compute the maximum-flow value, thencompute an actual maximum flow.]. We can speed up the Edmonds-Karp “fattest path” algorithm, at least for
networks with small integer capacities, by relaxing our requirements forthe next augmenting path. Instead of finding the augmenting path withmaximum bottleneck capacity, we find a path whose bottleneck capacity is
at least half of maximum, using the following capacity scaling algorithm.
(This algorithm was actually proposed by Edmonds and Karp.)
Assume all the edge capacities are positive integers less than U = 2k forsome integer k. The scaling algorithm maintains a bottleneck threshold ;initially, we set
U. In each phase, the algorithm augments along paths
from s to t in which every edge has residual capacity at least . When there
is no such path, the phase ends, we set
b /2c, and the next phasebegins. The algorithm ends when = 0.
(a) How many phases will this algorithm execute in the worst case?
(b) Let f be the flow at the end of a phase for a particular value of . Provethat the capacity of a minimum cut in the residual graph G f is at mostE· .
(c) Prove that in each phase of the scaling algorithm, there are at most 2E
augmentations.

(d) What is the overall running time of the capacity scaling algorithm?

���