7. N ETWORK F LOW I 7.

N ETWORK F LOW I

‣ max-flow and min-cut problems ‣ max-flow and min-cut problems

‣ Ford–Fulkerson algorithm ‣ Ford–Fulkerson algorithm
‣ max-flow min-cut theorem ‣ max-flow min-cut theorem
‣ capacity-scaling algorithm ‣ capacity-scaling algorithm
‣ shortest augmenting paths ‣ shortest augmenting paths
‣ Dinitz’ algorithm ‣ Dinitz’ algorithm
‣ simple unit-capacity networks ‣ simple unit-capacity networks
SECTION 7.1
Lecture slides by Kevin Wayne
Copyright © 2005 Pearson-Addison Wesley
http://www.cs.princeton.edu/~wayne/kleinberg-tardos

Last updated on 11/1/21 4:31 PM

Flow network Minimum-cut problem

A flow network is a tuple G = (V, E, s, t, c). Def. An st-cut (cut) is a partition (A, B) of the nodes with s ∈ A and t ∈ B.
・Digraph (V, E) with source s ∈ V and sink t ∈ V.
・Capacity c(e) ≥ 0 for each e ∈ E. assume all nodes are reachable from s
Def. Its capacity is the sum of the capacities of the edges from A to B.

Intuition. Material flowing through a transportation network; cap(A, B) = c(e)

e A
material originates at source and is sent to sink.

capacity
9

4 15 15 10
10 10

s 5 8 10 t s 5 t

15 15
4 6 15 10

16
capacity = 10 + 5 + 15 = 30
3 4
Minimum-cut problem Minimum-cut problem

Def. An st-cut (cut) is a partition (A, B) of the nodes with s ∈ A and t ∈ B. Def. An st-cut (cut) is a partition (A, B) of the nodes with s ∈ A and t ∈ B.

Def. Its capacity is the sum of the capacities of the edges from A to B. Def. Its capacity is the sum of the capacities of the edges from A to B.

cap(A, B) = c(e) cap(A, B) = c(e)

e A e A

Min-cut problem. Find a cut of minimum capacity.

10 10

s 8 t s 8 t

don’t include edges

from B to A 10

16
capacity = 10 + 8 + 16 = 34 capacity = 10 + 8 + 10 = 28
5 6

Network flow: quiz 1 Maximum-flow problem

Which is the capacity of the given st-cut? Def. An st-flow (flow) f is a function that satisfies:

A. 11 (20 + 25 − 8 − 11 − 9 − 6) ・For each e ∈ E : 0 f (e) c(e) [capacity]

・For each v ∈ V – {s, t} : f (e) = f (e) [flow conservation]
B. 34 (8 + 11 + 9 + 6) e v e v

C. 45 (20 + 25)

D. 79 (20 + 25 + 8 + 11 + 9 + 6)
flow capacity

inflow at v = 5 + 5 + 0 = 10
5/9 outflow at v = 10 + 0 = 10
capacity

5 5
s 20 8 10 10 0/4 /1 0 / 15 /
10
/ 5
10

s 5/5 5/8 v 10 / 10 t
6 12 8 11 9 8
6
10
/ 0 0 / 15 10
15 0/4 /6 /
10

1 16 25 t
10 / 16
7 8
 Maximum-flow problem Maximum-flow problem

Def. An st-flow (flow) f is a function that satisfies: Def. An st-flow (flow) f is a function that satisfies:
・For each e ∈ E : 0 f (e) c(e) [capacity] ・For each e ∈ E : 0 f (e) c(e) [capacity]
・For each v ∈ V – {s, t} : e v
f (e) =
e v
f (e) [flow conservation] ・For each v ∈ V – {s, t} : e v
f (e) =
e v
f (e) [flow conservation]

Def. The value of a flow f is: val(f ) = f (e) f (e) Def. The value of a flow f is: val(f ) = f (e) f (e)
e s e s e s e s

Max-flow problem. Find a flow of maximum value.

5/9 8/9

5 5 2 8
10 0/4 /1 0 / 15 /
10 10 0/4 /1 0 / 15 /
10
/ 5 / 5
10 10

s 5/5 5/8 10 / 10 t s 5/5 8/8 10 / 10 t

10 13
/ 0 0 / 15 10 / 3 0 / 15 10
15 0/4 /6 / 15 0/4 /6 /
10 10

value = 5 + 10 + 10 = 25 value = 10 + 5 + 13 = 28
10 / 16 13 / 16
9 10

Toward a max-flow algorithm

Greedy algorithm.
7. N ETWORK F LOW I ・Start with f (e) = 0 for each edge e ∈ E.
・Find an s↝t path P where each edge has f (e) < c(e).
‣ max-flow and min-cut problems ・Augment flow along path P.
‣ Ford–Fulkerson algorithm ・Repeat until you get stuck.
‣ max-flow min-cut theorem
‣ capacity-scaling algorithm
‣ shortest augmenting paths flow capacity
flow network G and flow f
‣ Dinitz’ algorithm
0/4
‣ simple unit-capacity networks
SECTION 7.1
0
0 /
10 0/2 /8 0/6 10
/
0 value of flow

s 0 / 10 0/9 0 / 10 t 0

12
Toward a max-flow algorithm Toward a max-flow algorithm

Greedy algorithm. Greedy algorithm.

・Start with f (e) = 0 for each edge e ∈ E. ・Start with f (e) = 0 for each edge e ∈ E.
・Find an s↝t path P where each edge has f (e) < c(e). ・Find an s↝t path P where each edge has f (e) < c(e).
・Augment flow along path P. ・Augment flow along path P.
・Repeat until you get stuck. ・Repeat until you get stuck.

flow network G and flow f flow network G and flow f

0/4 0/4

8
0 — 0
0 / 0 /
10 0/2 /8 0/6 10 8 10 0/2 /8 0/6 10
/ /
0 0
—

8
s 0 / 10 0/9 0 / 10 t 0 s 0 / 10 0/9 —
0 / 10 t 0 +8=8

13 14

Toward a max-flow algorithm Toward a max-flow algorithm

Greedy algorithm. Greedy algorithm.

・Start with f (e) = 0 for each edge e ∈ E. ・Start with f (e) = 0 for each edge e ∈ E.
・Find an s↝t path P where each edge has f (e) < c(e). ・Find an s↝t path P where each edge has f (e) < c(e).
・Augment flow along path P. ・Augment flow along path P.
・Repeat until you get stuck. ・Repeat until you get stuck.

flow network G and flow f flow network G and flow f

0/4 0/4

6
0 —
0
10 2 —
0/2 8 0/6 / 10 2/2 8 6 —
0/6 /
10 /
/8 10 / /8 10
8
— 10

2 10 6 8
s 0 / 10 —
0/9 —8 / 10 t 8 + 2 = 10 s —
0 / 10 —
2/9 10 / 10 t 10 + 6 = 16

15 16
Toward a max-flow algorithm Toward a max-flow algorithm

Greedy algorithm. Greedy algorithm.

・Start with f (e) = 0 for each edge e ∈ E. ・Start with f (e) = 0 for each edge e ∈ E.
・Find an s↝t path P where each edge has f (e) < c(e). ・Find an s↝t path P where each edge has f (e) < c(e).
・Augment flow along path P. ・Augment flow along path P.
・Repeat until you get stuck. ・Repeat until you get stuck.

ending flow value = 16 but max-flow value = 19

flow network G and flow f flow network G and flow f

0/4 3/4

6 9
10 2/2 8
/8 6/6 / 10 0/2 7
/8 6/6 /
/ 10 / 10
10 10

s 6 / 10 8/9 10 / 10 t 16 s 9 / 10 9/9 10 / 10 t 19

17 18

Why the greedy algorithm fails Residual network

Q. Why does the greedy algorithm fail? Original edge. e = (u, v) ∈ E. original flow network G
A. Once greedy algorithm increases flow on an edge, it never decreases it. ・Flow f (e). 6 / 17
・Capacity c(e).
u v

Ex. Consider flow network G . flow capacity

・The unique max flow f * has f *(v, w) = 0. Reverse edge. e reverse = (v, u).
・Greedy algorithm could choose s→v→w→t as first path. ・“Undo” flow sent.
residual network Gf residual
flow network G
Residual capacity. capacity

v 2 t (
<latexit sha1_base64="YJfOSbURwSXvCUYEAycBJsfVqD0=">AAACrnicbVBdi9NAFJ3ErzV+bHd9Ul8Gi7I+WBJZdF+EBRF8XMF2F5oYJrc37bCTSZi5kZaQN/+kf8Ff4STNg229MHA459w5MyerlLQUhr89/87de/cfHD0MHj1+8vR4dHI6s2VtAKdQqtLcZMKikhqnJEnhTWVQFJnC6+z2c6df/0RjZam/06bCpBBLLXMJghyVjn5Bmp/hW/4piDNcSt2Au8y2AXTkO95rb3hMuKZG5rzlyGOp+Zc4Dpz2o9kqBrsMbNt984Fhu83deox6MaSlo3E4CfvhhyAawJgNc5WeeKfxooS6QE2ghLXzKKwoaYQhCQrbIK4tVgJuxRLnDmpRoE2avq6Wv3bMguelcUcT79l/NxpRWLspMucsBK3svtaR/9PmNeUXSSN1VRNq2AblteJU8q57vpAGgdTGAQFGurdyWAkjgFw5Oyn93RXCzk+ada0llAvcYxWtyYiuxWi/s0Mwez+JPkzOv52PLy+GPo/YS/aKnbGIfWSX7Cu7YlMG7I838p57L/zQn/mJn26tvjfsPGM746/+Aodl0mY=</latexit>

u 11 v
c(e) f (e) e2E
cf (e) = 6
f (e ) e 2E
reverse edge
2 1 2
edges with positive
residual capacity

s 2 w Residual network. G f = (V, Ef , s, t, cf ). where flow on a reverse edge

・Ef = {e : f (e) < c(e)} ∪ {e :

negates flow on
> 0}. f (e reverse) corresponding forward edge

・Key property: f ʹ is a flow in G f iff f + f ʹ is a flow in G.

Bottom line. Need some mechanism to “undo” a bad decision. 19 20
Augmenting path Network flow: quiz 2

Def. An augmenting path is a simple s↝t path in the residual network G f . Which is the augmenting path of highest bottleneck capacity?

A. A→F→G→H
Def. The bottleneck capacity of an augmenting path P is the minimum
residual capacity of any edge in P. B. A→B→C→D →H

C. A→F→B→G→H
Key property. Let f be a flow and let P be an augmenting path in G f .
D. A→F→B→G→ C→D→H
Then, after calling f ʹ ← AUGMENT( f, c, P), the resulting f ʹ is a flow and
val( f ʹ) = val( f ) + bottleneck(G f, P).

AUGMENT( f, c, P) residual capacity

________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
5

δ ← bottleneck capacity of augmenting path P. A 9 B 8 C 6 D

FOREACH edge e ∈ P : source

IF (e ∈ E) f (e) ← f (e) + δ. 5 7 8 7 4 5 6 8 5

ELSE f (ereverse) ← f (ereverse) – δ.

RETURN f. E 5 F G H
________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
2 3

21 5 target 22

Ford–Fulkerson algorithm

Ford–Fulkerson augmenting path algorithm.

・Start with f (e) = 0 for each edge e ∈ E. 7. N ETWORK F LOW I
・Find an s↝t path P in the residual network G f .
・Augment flow along path P. ‣ max-flow and min-cut problems
・Repeat until you get stuck. ‣ Ford–Fulkerson algorithm
‣ max-flow min-cut theorem
FORD–FULKERSON(G) ‣ capacity-scaling algorithm
________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
_

FOREACH edge e ∈ E : f (e) ← 0. ‣ shortest augmenting paths

G f ← residual network of G with respect to flow f. ‣ Dinitz' algorithm
WHILE (there exists an s↝t path P in G f )
‣ simple unit-capacity networks
f ← AUGMENT( f, c, P). SECTION 7.2

Update G f. augmenting path

RETURN f.

23
Relationship between flows and cuts Relationship between flows and cuts

Flow value lemma. Let f be any flow and let (A, B) be any cut. Then, Flow value lemma. Let f be any flow and let (A, B) be any cut. Then,
the value of the flow f equals the net flow across the cut (A, B). the value of the flow f equals the net flow across the cut (A, B).

val(f ) = f (e) f (e) val(f ) = f (e) f (e)

e A e A e A e A

net flow across cut = 5 + 10 + 10 = 25 net flow across cut = 10 + 5 + 10 = 25

5/9 5/9

5 5 5 5
10 0/4 /1 0 / 15 /
10 10 0/4 /1 0 / 15 /
10
/ 5 / 5
10 10

s 5/5 5/8 10 / 10 t value of flow = 25 s 5/5 5/8 10 / 10 t value of flow = 25

10 10
/ 0 0 / 15 10 / 0 0 / 15 10
15 0/4 /6 / 15 0/4 /6 /
10 10

10 / 16 10 / 16
25 26

Relationship between flows and cuts Network flow: quiz 3

Flow value lemma. Let f be any flow and let (A, B) be any cut. Then, Which is the net flow across the given cut?
the value of the flow f equals the net flow across the cut (A, B).
A. 11 (20 + 25 − 8 − 11 − 9 − 6)

val(f ) = f (e) f (e) B. 26 (20 + 22 − 8 − 4 − 4)

e A e A
C. 42 (20 + 22)

D. 45 (20 + 25)
net flow across cut = (10 + 10 + 5 + 10 + 0 + 0) – (5 + 5 + 0 + 0) = 25

5/9

edges from B to A flow capacity

5 5
10 0/4 /1 0 / 15 /
10
/ 5
10 s 20 / 20 8/8 4 / 10

s 5/5 5/8 10 / 10 t value of flow = 25

5 4
1/6 / 8/8 / 4/9 6 4/8
12 11 /
10
0
/ 0 0 / 15 10
15 0/4 /6 /
10

1/1 14 / 16 22 / 25 t
10 / 16
27 28
Relationship between flows and cuts Relationship between flows and cuts

Flow value lemma. Let f be any flow and let (A, B) be any cut. Then, Weak duality. Let f be any flow and (A, B) be any cut. Then, val( f ) ≤ cap(A, B).
the value of the flow f equals the net flow across the cut (A, B). Pf.
val(f ) = f (e) f (e)
e A e A
val(f ) = f (e) f (e)
e A e A f (e)
flow value
lemma e A

c(e)
Pf. val(f ) = f (e) f (e) e A
e s e s
= cap(A, B) ▪
by flow conservation, all terms
except for v = s are 0
= f (e) f (e)
8/9
v A e v e v
2 8
/1 /
10 0/4 5 0 / 15 10
/ 10
val(f ) = f (e) f (e) 10
▪
e A e A
s 5/5 7/8 9 / 10 t s 5 t

12
2
/
15 0/4 /6 0 / 15 10 15
/
10

12 / 16

29 value of flow = 27 ≤ capacity of cut = 30 30

Certificate of optimality Max-flow min-cut theorem

Corollary. Let f be a flow and let (A, B) be any cut. Max-flow min-cut theorem. Value of a max flow = capacity of a min cut.
If val( f ) = cap(A, B), then f is a max flow and (A, B) is a min cut. strong duality

weak duality
Pf.
・For any flow f ʹ: val( f ʹ) ≤ cap(A, B) = val( f ).
・For any cut (Aʹ, Bʹ): cap(Aʹ, Bʹ) ≥ val( f ) = cap(A, B). ▪

weak duality

8/9

2
/1
8 1956 IRE TRANXACTIONX ON INFORiMATION THEORY 117
/
10 0/4 5 0 / 15 10
/ 10
10
A Note on the Maximum Flow Through a Network*
P. ELIASt, A. FEINSTEINI, AND C. E. SHANNON!
s 5/5 8/8 10 / 10 t s 8 t

13 Summary--This note discusses the problem of maximizing the

3 from one terminal to the other in the original network
/
15 0/4 /6 0 / 15 10 rate of flow from one terminal to another, through a network which
passes through at least one branch in the cut-set. In the
/ 10 consists of a number of branches, each of which has a !imited capa-
10 city. The main result is a theorem: The maximum possible flow from network above, some examples of cut-sets are (d, e, f),
left to right through a network is equal to the minimum value among and (b, c, e, g, h), (d, g, h, i) . By a simple cut-set we will
all simple cut-sets. This theorem is applied to solve a more general
problem, in which a number of input nodes and a number of output mean a cut-set such that if any branch is omitted it is no
13 / 16 nodes are used. longer a cut-set. Thus (d, e, f) and (b, c, e, g, h) are simple
cut-sets while (d, g, h, ;) is not. When a simple cut-set is
ONSIDER a two-terminal network such as that deleted from a connected two-terminal network, the net-
of Fig. 1. The branches of the network might work falls into exactly two parts, a left part containing the
c represent communication channels, or, more
value of flow = 28 = capacity of cut = 28 31
generally, any conveying system of limited capacity as,
left terminal and a right part containing the right terminal.
We assign a value to a simple cut-set by taking the sum of
32
for example, a railroad system, a power feeding system, capacities of branches in the cut-set, only counting
or a network of pipes, provided in each case it is possible capacities, however, from the left part to the right part
to assign a definite maximum allowed rate of flow over a for branches that are unidirectional. Note that the
given branch. The links may be of two types, either one direction of an unidirectional branch cannot be deduced
directional (indicated by arrows) or two directional, in from its appearance in the graph of the network. A branch
 Max-flow min-cut theorem Max-flow min-cut theorem

Max-flow min-cut theorem. Value of a max flow = capacity of a min cut. Max-flow min-cut theorem. Value of a max flow = capacity of a min cut.
Augmenting path theorem. A flow f is a max flow iff no augmenting paths. Augmenting path theorem. A flow f is a max flow iff no augmenting paths.

Pf. The following three conditions are equivalent for any flow f : Pf. The following three conditions are equivalent for any flow f :
i. There exists a cut (A, B) such that cap(A, B) = val( f ). i. There exists a cut (A, B) such that cap(A, B) = val( f ).
ii. f is a max flow. ii. f is a max flow.
if Ford–Fulkerson terminates,
iii. There is no augmenting path with respect to f. then f is max flow
iii. There is no augmenting path with respect to f.

[ i ⇒ ii ] [ ii ⇒ iii ] We prove contrapositive: ¬ iii ⇒ ¬ ii.

・This is the weak duality corollary. ▪ ・Suppose that there is an augmenting path with respect to f.
・Can improve flow f by sending flow along this path.
・Thus, f is not a max flow. ▪

33 34

Max-flow min-cut theorem Computing a minimum cut from a maximum flow

[ iii ⇒ i ] Theorem. Given any max flow f , can compute a min cut (A, B) in O(m) time.
・Let f be a flow with no augmenting paths. Pf. Let A = set of nodes reachable from s in residual network G f . ▪
・Let A = set of nodes reachable from s in residual network G f. argument from previous slide implies that
・By definition of A: s ∈ A. capacity of (A, B) = value of flow f

・By definition of flow f: t ∉ A. edge e = (v, w) with v ∈ B, w ∈ A

must have f(e) = 0 8
original flow network G
1
val(f ) = f (e) f (e)
A B
e A e A 8
13
flow value 10 15 2
t 4
lemma = c(e) 0 2
<latexit sha1_base64="ZTUKVGmMjB/WcCE6Tg9AU4sscGI=">AAACWXicbVDBThsxEPUupaRpKQGOvViNKtEDYRchgVRVAnHhSCWSIGWjyOvMgoXXXtnjKtFqP6NfwxU+AvEzeJMcmoQn2Xp6b8bjeWkhhcUoegnCjQ+bH7can5qfv2x/3Wnt7vWsdoZDl2upzW3KLEihoIsCJdwWBlieSuinD5e13/8LxgqtbnBawDBnd0pkgjP00qh19Jsmv2hiXT4qgSYIEyypdkh1Rit6UVF+AD/rksP6ipqjVjvqRDPQdRIvSJsscD3aDfaSseYuB4VcMmsHcVTgsGQGBZdQNRNnoWD8gd3BwFPFcrDDcrZZRX94ZUwzbfxRSGfq/x0ly62d5qmvzBne21WvFt/zBg6zs2EpVOEQFJ8PypykqGkdEx0LAxzl1BPGjfB/pfyeGcbRh7k0ZfZ2AXxpk3LilOB6DCuqxAkaVvkU49XM1knvuBNHnfjPSfv8bJFng3wj38kBickpOSdX5Jp0CSf/yCN5Is/BaxiEjbA5Lw2DRc8+WUK4/wZJQ7Me</latexit>
e A

A s 5 8 10 t
= cap(A, B) s
15
2 3 1 6
10
13

edge e = (v, w) with v ∈ A, w ∈ B

16
must have f(e) = c(e)

35 36
 Analysis of Ford–Fulkerson algorithm (when capacities are integral)

Assumption. Every edge capacity c(e) is an integer between 1 and C.

7. N ETWORK F LOW I
Integrality invariant. Throughout Ford–Fulkerson, every edge flow f (e)
‣ max-flow and min-cut problems and residual capacity cf (e) is an integer.
Pf. By induction on the number of augmenting paths. ▪
‣ Ford–Fulkerson algorithm
consider cut A = { s }
(assumes no parallel edges)

‣ max-flow min-cut theorem Theorem. Ford–Fulkerson terminates after at most val( f *) ≤ n C

‣ capacity-scaling algorithm augmenting paths, where f * is a max flow.
Pf. Each augmentation increases the value of the flow by at least 1. ▪
‣ shortest augmenting paths
‣ Dinitz' algorithm Corollary. The running time of Ford–Fulkerson is O(m n C).
‣ simple unit-capacity networks Pf. Can use either BFS or DFS to find an augmenting path in O(m) time. ▪
SECTION 7.3
f(e) is an integer for every e

Integrality theorem. There exists an integral max flow f *.

Pf. Since Ford–Fulkerson terminates, theorem follows from integrality
invariant (and augmenting path theorem). ▪
38

Ford–Fulkerson: exponential example Network flow: quiz 4

Q. Is generic Ford–Fulkerson algorithm poly-time in input size? The Ford–Fulkerson algorithm is guaranteed to terminate if the edge
m, n, and log C capacities are …
A. No. If max capacity is C, then algorithm can take ≥ C iterations.
・s→v→w→t A. Rational numbers.
・s→w→v→t
Let D denote the product (or lcm) of the denominators.
each augmenting path
Then, every edge flow f (e) and every residual capacity cf (e)
sends only 1 unit of flow
・s→v→w→t (# augmenting paths = 2C)
s
B. Real numbers. is a multiple of 1 / D.

・s→w→v→t C. Both A and B.

・…
・s→v→w→t
D. Neither A nor B.
C
C

・s→w→v→t
v 1 w
C

t
39 40
Choosing good augmenting paths Choosing good augmenting paths

Use care when selecting augmenting paths. Choose augmenting paths with:
・Some choices lead to exponential algorithms. ・Max bottleneck capacity (“fattest”). how to find?

・Clever choices lead to polynomial algorithms. ・Sufficiently large bottleneck capacity. next

・Fewest edges. ahead

Pathology. When edge capacities can be irrational, no guarantee

that Ford–Fulkerson terminates (or converges to a maximum flow)! Theoretical Improvements in Algorithmic Efficiency
for Network Flow Problems

JACK EDMONDS

University of Waterloo, Waterloo, Ontario, Canada

Goal. Choose augmenting paths so that: AND

・Can find augmenting paths efficiently.

RICHARD M. K A R P

University of California, Berkeley, California

・Few iterations. ABSTRACT. This paper presents new algorithms for t h e m a x i m u m flow problem, the Hitchcock
t r a n s p o r t a t i o n problem, and t h e general m i n i m u m - c o s t flow problem. U p p e r bounds on the
numbers of steps in these algorithms are derived, and are shown to compale favorably with
upper bounds on t h e numbers of steps required by earlier algorithms.
First, the paper states the m a x i m u m flow problem, gives the F o r d - F u l k e r s o n labeling method
for its solution, and points out t h a t an improper choice of flow a u g m e n t i n g p a t h s can lead to
Edmonds-Karp 1972 (USA)
severe c o m p u t a t i o n a l difficulties. T h e n rules of choice t h a t avoid these difficulties are given.
We show t h a t , if each flow a u g m e n t a t i o n is made along an a u g m e n t i n g p a t h h a v i n g a minimum Dinitz 1970 (Soviet Union)
n u m b e r of arcs, t h e n a m a x i m u m flow in an n-node network will be o b t a i n e d a f t e r no more t h a n
~(n a - n) a u g m e n t a t i o n s ; and t h e n we show t h a t if each flow change is chosen to produce a
m a x i m u m increase in the flow value then, provided the capacities are integral, a m a x i m u m flow
will be d e t e r m i n e d within at most 1 + logM/(M--1) if(t, S) a u g m e n t a t i o n s , wheref*(t, s) is the
value of the maximum flow and M is the m a x i m u m n u m b e r of arcs across a cut.
Next a new algorithm is given for the m i n i m u m - c o s t flow problem, in which all s h o r t e s t - p a t h
c o m p u t a t i o n s are performed on networks with all weights nonnegative. In particular, this
a l g o r i t h m solves the n X n assigmnent problem in O(n3) steps. Following t h a t we explore a invented in response to a class
" s c a l i n g " technique for solving a minimum-cost flow problem by t r e a t i n g a sequence of derived
problems w i t h "scaled d o w n " capacities. It is shown t h a t , using this technique, the solution of exercises by Adel’son-Vel’skiĭ
a I i i t c h c o c k t r a n s p o r t a t i o n problem w i t h m sources and n sinks, m ~ n, and m a x i m u m flow B,
requires at most (n + 2) log2 (B/n) flow a u g m e n t a t i o n s . Similar results are also given for the
41 general minimum-cost flow problem. 42
An a b s t r a c t s t a t i n g the main results of the present paper was presented at the Calgary
I n t e r n a t i o n a l Conference on C o m b i n a t o r i a l Structures and T h e i r Applications, J u n e 1969.
In a paper b y l)inic (1970) a result closely related to the main result of Section 1.2 is obtained.
Dinic shows t h a t , in a network with n nodes and p arcs, a m a x i m u m flow can be computed in
0 (n2p) primitive operations b y an algorithm which a u g m e n t s along s h o r t e s t augmenting paths.
KEY WOl¢l)S AND PHP~ASES: network flows, t r a n s p o r t a t i o n problem, analysis of algorithms
CR CATEGOI{.IES: 5.3, 5.4, 8.3

Capacity-scaling algorithm Capacity-scaling algorithm

Copyright © 1972, Association for C o m p u t i n g Machinery, Inc.
General permission to republish, b u t not for profit, all or p a r t of this m a t e r i a l is granted,
provided t h a t reference is made to this publication, to its date of issue, and to the fact t h a t
r e p r i n t i n g privileges were granted by permission of the Association for C o m p u t i n g Machinery.
Authors' addresses : J. Edmonds, D e p a r t m e n t of Combinatorics and Optimization, University
of Waterloo, Waterloo, Ontario, C a n a d a ; R. M. Karp, College of Engineering, Operations

Overview. Choosing augmenting paths with “large” bottleneck capacity. Research Center, U n i v e r s i t y of California, Berkeley, CA 94720; the l a t t e r a u t h o r ' s research has
been partially s u p p o r t e d by the N a t i o n a l Science F o u n d a t i o n raider G r a n t GP-15473 with the

・Maintain scaling parameter Δ.

U n i v e r s i t y of California.

though not necessarily largest CAPACITY-SCALING(G)

・
Jc~urnal of the Associationfor Computing Machinery, Vol. 19, No. 2, Apri| 1972. pp. 248-264.

Let G (Δ) be the part of the residual network containing

__________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

f
FOREACH edge e ∈ E : f (e) ← 0.
only those edges with capacity ≥ Δ.
・Any augmenting path in G f (Δ) has bottleneck capacity ≥ Δ.
Δ ← largest power of 2 ≤ C.

WHILE (Δ ≥ 1)
s s G f (Δ) ← Δ-residual network of G with respect to flow f .
WHILE (there exists an s↝t path P in G f (Δ))
f ← AUGMENT( f, c, P).
0
0

10
10

11
11

2
2

Update G f (Δ). Δ-scaling phase

1 Δ ← Δ / 2.
0
0

RETURN f.
12
12

17
17

2
2

__________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

t t

Gf Gf (Δ), Δ = 100 43 44
 Capacity-scaling algorithm: proof of correctness Capacity-scaling algorithm: analysis of running time

Assumption. All edge capacities are integers between 1 and C. Lemma 1. There are 1 + ⎣log2 C⎦ scaling phases.
Pf. Initially C / 2 < Δ ≤ C; Δ decreases by a factor of 2 in each iteration. ▪
Invariant. The scaling parameter Δ is a power of 2.
Pf. Initially a power of 2; each phase divides Δ by exactly 2. ▪ Lemma 2. Let f be the flow at the end of a Δ-scaling phase.
Then, the max-flow value ≤ val( f ) + m Δ.
Integrality invariant. Throughout the algorithm, every edge flow f (e) and Pf. Next slide.
residual capacity cf (e) is an integer.
Pf. Same as for generic Ford–Fulkerson. ▪ Lemma 3. There are ≤ 2m augmentations per scaling phase.
or equivalently,
Pf. at the end

Theorem. If capacity-scaling algorithm terminates, then f is a max flow. ・Let f be the flow at the beginning of a Δ-scaling phase. of a 2Δ-scaling phase

Pf. ・Lemma 2 ⇒ max-flow value ≤ val( f ) + m (2 Δ).

・By integrality invariant, when Δ = 1 ⇒ G f (Δ) = G f . ・Each augmentation in a Δ-phase increases val( f ) by at least Δ. ▪
・Upon termination of Δ = 1 phase, there are no augmenting paths.
・Result follows augmenting path theorem ▪ Theorem. The capacity-scaling algorithm takes O(m2 log C) time.
Pf.
・Lemma 1 + Lemma 3 ⇒ O(m log C) augmentations.
45 ・Finding an augmenting path takes O(m) time. ▪ 46

Capacity-scaling algorithm: analysis of running time

Lemma 2. Let f be the flow at the end of a Δ-scaling phase.

Then, the max-flow value ≤ val( f ) + m Δ. 7. N ETWORK F LOW I
Pf.
・We show there exists a cut (A, B) such that cap(A, B) ≤ val( f ) + m Δ. ‣ max-flow and min-cut problems
・Choose A to be the set of nodes reachable from s in G f (Δ). ‣ Ford–Fulkerson algorithm
・By definition of A: s ∈ A.
‣ max-flow min-cut theorem
・By definition of flow f: t ∉ A. edge e = (v, w) with v ∈ B, w ∈ A
must have f(e) < Δ
original flow network ‣ capacity-scaling algorithm
val(f ) = f (e) f (e) A B ‣ shortest augmenting paths
e A e A
flow value
t
‣ Dinitz’ algorithm
lemma (c(e) )
e A e A ‣ simple unit-capacity networks
SECTION 17.2
c(e) s
e A e A e A

cap(A, B) m
edge e = (v, w) with v ∈ A, w ∈ B
must have f(e) > c(e) – Δ
47
Shortest augmenting path Shortest augmenting path: overview of analysis

Q. How to choose next augmenting path in Ford–Fulkerson? Lemma 1. The length of a shortest augmenting path never decreases.
A. Pick one that uses the fewest edges. Pf. Ahead.
number of edges

can find via BFS

Lemma 2. After at most m shortest-path augmentations, the length of a
shortest augmenting path strictly increases.
Pf. Ahead.
SHORTEST-AUGMENTING-PATH(G)
_________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

FOREACH e ∈ E : f (e) ← 0. Theorem. The shortest-augmenting-path algorithm takes O(m2 n) time.

G f ← residual network of G with respect to flow f. Pf.
WHILE (there exists an s↝t path in G f ) ・O(m) time to find a shortest augmenting path via BFS.
P ← BREADTH-FIRST-SEARCH(G f ). ・There are ≤ m n augmentations.
f ← AUGMENT( f, c, P). - at most m augmenting paths of length k Lemma 1 + Lemma 2

- at most n−1 different lengths ▪

Update G f.
RETURN f. augmenting paths are simple paths
_________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

49 50

Shortest augmenting path: analysis Network flow: quiz 5

Def. Given a digraph G = (V, E) with source s, its level graph is defined by: Which edges are in the level graph of the following digraph?
・ℓ(v) = number of edges in shortest s↝v path.
・LG = (V, EG) is the subgraph of G that contains only those edges (v, w) ∈ E A. D→F.
with ℓ(w) = ℓ(v) + 1.
B. E→F.

C. Both A and B.
graph G

D. Neither A nor B.

1 3
s t
B D

level graph LG

s t source A C E F sink

ℓ= 0 ℓ= 1 ℓ= 2 ℓ= 3 51
0 1 2 3
52
Shortest augmenting path: analysis Shortest augmenting path: analysis

Def. Given a digraph G = (V, E) with source s, its level graph is defined by: Lemma 1. The length of a shortest augmenting path never decreases.
・ℓ(v) = number of edges in shortest s↝v path. ・Let f and f ʹ be flow before and after a shortest-path augmentation.
・LG = (V, EG) is the subgraph of G that contains only those edges (v, w) ∈ E ・Let LG and LG ʹ be level graphs of G f and G f ʹ .
with ℓ(w) = ℓ(v) + 1. ・Only back edges added to G f ′
(any s↝t path that uses a back edge is longer than previous length) ▪

Key property. P is a shortest s↝v path in G iff P is an s↝v path in LG. level graph LG

s t

ℓ= 0 ℓ= 1 ℓ= 2 ℓ= 3
level graph LG
level graph LG′

s t

ℓ= 0 ℓ= 1 ℓ= 2 ℓ= 3 53
s t
54

Shortest augmenting path: analysis Shortest augmenting path: review of analysis

Lemma 2. After at most m shortest-path augmentations, the length of a Lemma 1. Throughout the algorithm, the length of a shortest augmenting
shortest augmenting path strictly increases. path never decreases.
・At least one (bottleneck) edge is deleted from LG per augmentation.
・No new edge added to LG until shortest path length strictly increases. ▪ Lemma 2. After at most m shortest-path augmentations, the length of a
shortest augmenting path strictly increases.

level graph LG Theorem. The shortest-augmenting-path algorithm takes O(m2 n) time.

s t

ℓ= 0 ℓ= 1 ℓ= 2 ℓ= 3

level graph LG′

s t
55 56
Shortest augmenting path: improving the running time

Note. Θ(m n) augmentations necessary for some flow networks.

・Try to decrease time per augmentation instead. 7. N ETWORK F LOW I
・Simple idea ⇒ O(m n2 ) [Dinitz 1970] ahead

・Dynamic trees ⇒ O(m n log n) [Sleator–Tarjan 1983] ‣ max-flow and min-cut problems
JOURNAL OF COMPUTER AND SYSTEM SCIENCES 26, 362-391 (1983)
‣ Ford–Fulkerson algorithm
‣ max-flow min-cut theorem
A Data Structure for Dynamic Trees

DANIEL D. SLEATOR AND ROBERT ENDRE TARJAN ‣ capacity-scaling algorithm

‣ shortest augmenting paths
Bell Laboratories, Murray Hill, New Jersey 07974

Received May 8, 1982; revised October 18, 1982

A data structure is proposed to maintain a collection of vertex-disjoint trees under a

‣ Dinitz’ algorithm
sequence of two kinds of operations: a link operation that combines two trees into one by
adding an edge, and a cut operation
operation requires
that divides one tree into two by deleting an edge. Each
O(log n) time. Using this data structure, new fast algorithms are obtained ‣ simple unit-capacity networks
for the following problems:
SECTION 18.1
(1) Computing nearest common ancestors.
(2) Solving various network flow problems including finding maximum flows, blocking
flows, and acyclic flows.
(3) Computing certain kinds of constrained minimum spanning trees.
(4) Implementing the network simplex algorithm for minimum-cost flows.
The most significant application is (2); an O(mn log n)-time algorithm is obtained to find a
maximum flow in a network of n vertices and m edges, beating by a factor of log n the fastest
algorithm previously known for sparse graphs.

1. INTR~DIJCTI~N 57

In this paper we consider the following problem: We are given a collection of

vertex-disjoint rooted trees. We want to represent the trees by a data structure that
allows us to easily extract certain information about the trees and to easily update the
structure to reflect changes in the trees caused by three kinds of operations:
link(v, w): If u is a tree root and w is a vertex in another tree, link the trees
Dinitz’ algorithm containing v and w by adding the edge(v, w), making w the parent of v. Dinitz’ algorithm
cut(v): If node v is not a tree root, divide the tree containing v into two trees by
deleting the edge from v to its parent.
ever-t(v): Turn the tree containing vertex u “inside out” by making v the root of
the tree.
Two types of augmentations.
We propose a data structure that solves this dynamic trees problem. We give two
Two types of augmentations.
・Normal: length of shortest path does not change.
versions of the data structure. The first has a time bound of O(log n) per operation
when the time is amortized over a worst-case sequence of operations; the second, ・Normal: length of shortest path does not change.
・Special: length of shortest path strictly increases. ・Special: length of shortest path strictly increases.
362
0022-0000/83 $3.00
Copyright 0 1983 by Academic Press, Inc.
All rights of reproduction in any form reserved.

within a phase, length of shortest

Phase of normal augmentations. augmenting path does not change Phase of normal augmentations.
・Construct level graph LG. ・Construct level graph LG.
・Start at s, advance along an edge in LG until reach t or get stuck. ・Start at s, advance along an edge in LG until reach t or get stuck.
・If reach t, augment flow; update LG; and restart from s. ・If reach t, augment flow; update LG; and restart from s.
・If get stuck, delete node from LG and retreat to previous node. ・If get stuck, delete node from LG and retreat to previous node.

construct level graph advance

s t s t
level graph LG level graph LG
59 60
Dinitz’ algorithm Dinitz’ algorithm

Two types of augmentations. Two types of augmentations.

・Normal: length of shortest path does not change. ・Normal: length of shortest path does not change.
・Special: length of shortest path strictly increases. ・Special: length of shortest path strictly increases.
Phase of normal augmentations. Phase of normal augmentations.
・Construct level graph LG. ・Construct level graph LG.
・Start at s, advance along an edge in LG until reach t or get stuck. ・Start at s, advance along an edge in LG until reach t or get stuck.
・If reach t, augment flow; update LG; and restart from s. ・If reach t, augment flow; update LG; and restart from s.
・If get stuck, delete node from LG and retreat to previous node. ・If get stuck, delete node from LG and retreat to previous node.

augment advance
remove from level graph
edges with bottleneck capacity

s t s t
level graph LG level graph LG
61 62

Dinitz’ algorithm Dinitz’ algorithm

Two types of augmentations. Two types of augmentations.

・Normal: length of shortest path does not change. ・Normal: length of shortest path does not change.
・Special: length of shortest path strictly increases. ・Special: length of shortest path strictly increases.
Phase of normal augmentations. Phase of normal augmentations.
・Construct level graph LG. ・Construct level graph LG.
・Start at s, advance along an edge in LG until reach t or get stuck. ・Start at s, advance along an edge in LG until reach t or get stuck.
・If reach t, augment flow; update LG; and restart from s. ・If reach t, augment flow; update LG; and restart from s.
・If get stuck, delete node from LG and retreat to previous node. ・If get stuck, delete node from LG and retreat to previous node.

retreat advance

s t s t
level graph LG level graph LG
63 64
Dinitz’ algorithm Dinitz’ algorithm

Two types of augmentations. Two types of augmentations.

・Normal: length of shortest path does not change. ・Normal: length of shortest path does not change.
・Special: length of shortest path strictly increases. ・Special: length of shortest path strictly increases.
Phase of normal augmentations. Phase of normal augmentations.
・Construct level graph LG. ・Construct level graph LG.
・Start at s, advance along an edge in LG until reach t or get stuck. ・Start at s, advance along an edge in LG until reach t or get stuck.
・If reach t, augment flow; update LG; and restart from s. ・If reach t, augment flow; update LG; and restart from s.
・If get stuck, delete node from LG and retreat to previous node. ・If get stuck, delete node from LG and retreat to previous node.

augment advance

s t s t
level graph LG level graph LG
65 66

Dinitz’ algorithm Dinitz’ algorithm

Two types of augmentations. Two types of augmentations.

・Normal: length of shortest path does not change. ・Normal: length of shortest path does not change.
・Special: length of shortest path strictly increases. ・Special: length of shortest path strictly increases.
Phase of normal augmentations. Phase of normal augmentations.
・Construct level graph LG. ・Construct level graph LG.
・Start at s, advance along an edge in LG until reach t or get stuck. ・Start at s, advance along an edge in LG until reach t or get stuck.
・If reach t, augment flow; update LG; and restart from s. ・If reach t, augment flow; update LG; and restart from s.
・If get stuck, delete node from LG and retreat to previous node. ・If get stuck, delete node from LG and retreat to previous node.

retreat retreat

s t s t
level graph LG level graph LG
67 68
 Dinitz’ algorithm Dinitz’ algorithm (as refined by Even and Itai)

Two types of augmentations.

・Normal: length of shortest path does not change. INITIALIZE(G, f ) ADVANCE(v)
・Special: length of shortest path strictly increases.
_______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

LG ← level-graph of G f. IF (v = t)
P ← ∅. AUGMENT(P).
Phase of normal augmentations.
・Construct level graph LG. GOTO ADVANCE(s). Remove saturated edges from LG.

・Start at s, advance along an edge in LG until reach t or get stuck.

_______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

P ← ∅.

・If reach t, augment flow; update LG; and restart from s. GOTO ADVANCE(s).

・If get stuck, delete node from LG and retreat to previous node.
RETREAT(v)
_______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

IF (v = s) IF (there exists edge (v, w) ∈ LG)

STOP. Add edge (v, w) to P.

end of phase ELSE GOTO ADVANCE(w).

Delete v (and all incident edges) from LG.

ELSE
Remove last edge (u, v) from P.
GOTO RETREAT(v).
GOTO ADVANCE(u). ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

s t _______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

level graph LG
69 70

Network flow: quiz 6 Dinitz’ algorithm: analysis

How to compute the level graph LG efficiently? Lemma. A phase can be implemented to run in O(m n) time.
Pf.

A. Depth-first search. ・Initialization happens once per phase. O(m) using BFS

・At most m augmentations per phase. O(mn) per phase

B. Breadth-first search. (because an augmentation deletes at least one edge from LG)
C. Both A and B. ・At most n retreats per phase. O(m + n) per phase

(because a retreat deletes one node from LG)

・At most m n advances per phase.
D. Neither A nor B.
O(mn) per phase

(because at most n advances before retreat or augmentation) ▪

1 3

B D Theorem. [Dinitz 1970] Dinitz’ algorithm runs in O(m n2) time.

Pf.
・By Lemma, O(m n) time per phase.
・At most n−1 phases (as in shortest-augmenting-path analysis). ▪

source A C E F sink

0 1 2 3
71 72
Augmenting-path algorithms: summary Maximum-flow algorithms: theory highlights

year method worst case discovered by

1951 simplex O(m n2 C) Dantzig

year method # augmentations running time
1955 augmenting paths O(m n C) Ford–Fulkerson
1955 augmenting path nC O(m n C)
1970 shortest augmenting paths O(m n2) Edmonds–Karp, Dinitz

1972 fattest path m log (mC) O(m2 log n log (mC)) 1974 blocking flows O(n3) Karzanov

1972 capacity scaling m log C O(m2 log C) fat paths 1983 dynamic trees O(m n log n) Sleator–Tarjan

1985 improved capacity scaling O(m n log C) Gabow

1985 improved capacity scaling m log C O(m n log C)
1988 push–relabel O(m n log (n2 / m)) Goldberg–Tarjan
1970 shortest augmenting path mn O(m n) 2
1998 binary blocking flows O(m3/2 log (n2 / m) log C) Goldberg–Rao

1970 level graph mn O(m n2 ) shortest paths 2013 compact networks O(m n) Orlin

1983 dynamic trees mn O(m n log n ) 2014 interior-point methods Õ(m n1/2 log C) Lee–Sidford

2016 electrical flows Õ(m10/7 C1/7) Mądry

augmenting-path algorithms with m edges, n nodes, and integer capacities between 1 and C

20xx

73 max-flow algorithms with m edges, n nodes, and integer capacities between 1 and C 74

Maximum-flow algorithms: practice Maximum-flow algorithms: practice

Push–relabel algorithm (SECTION 7.4). [Goldberg–Tarjan 1988] Caveat. Worst-case running time is generally not useful for predicting or
Increases flow one edge at a time instead of one augmenting path at a time. comparing max-flow algorithm performance in practice.

Best in practice. Push–relabel method with gap relabeling: O(m3/2) in practice.

A New Approach to the Maximum-Flow Problem

ANDREW V. GOLDBERG
Massachusetts Institute of Technology, Cambridge, Massachusetts

AND
On I m p l e m e n t i n g P u s h - R e l a b e l M e t h o d
ROBERT E. TARJAN for the M a x i m u m Flow P r o b l e m EUROPEAN
JOURNAL
OF OPERATIONAL
Princeton University, Princeton, New Jersey, and AT&T Bell Laboratories, Murray Hill, New Jersey Boris V. Cherkassky 1 and Andrew V. Goldberg 2 RESEARCH
ELSEVIER European Journal of Operational Research 97 (1997) 509-542
1 Central Institute for Economics and Mathematics,
Krasikova St. 32, 117418, Moscow, Russia
Abstract. All previously known efftcient maximum-flow algorithms work by finding augmenting paths, [email protected]
either one path at a time (as in the original Ford and Fulkerson algorithm) or all shortest-length 2 Computer Science Department, Stanford University Theory and Methodology
augmenting paths at once (using the layered network approach of Dinic). An alternative method based Stanford, CA 94305, USA
on the preflow concept of Karzanov is introduced. A preflow is like a flow, except that the total amount
goldberg~cs. stanford, edu Computational investigations of maximum flow algorithms
flowing into a vertex is allowed to exceed the total amount flowing out. The method maintains a preflow
Ravindra K . A h u j a a, M u r a l i K o d i a l a m b, A j a y K . M i s h r a c, J a m e s B . O r l i n d,.
in the original network and pushes local flow excess toward the sink along what are estimated to be A b s t r a c t . We study efficient implementations of the push-relabel method
shortest paths. The algorithm and its analysis are simple and intuitive, yet the algorithm runs as fast as for the maximum flow problem. The resulting codes are faster than the a Department t~'lndustrial and Management Engineering. Indian Institute of Technology. Kanpur, 208 016, India
b AT& T Bell Laboratories, Holmdel, NJ 07733, USA
any other known method on dense.graphs, achieving an O(n)) time bound on an n-vertex graph. By previous codes, and much faster on some problem families. The speedup c KA'F-ZGraduate School of Business, University of Pittsburgh, Pittsburgh, PA 15260, USA
is due to the combination of heuristics used in our implementations. We
incorporating the dynamic tree data structure of Sleator and Tarjan, we obtain a version of the algorithm also exhibit a family of problems for which the running time of all known
d Sloun School of Management, Massachusetts Institute of Technology. Cambridge. MA 02139. USA

running in O(nm log(n’/m)) time on an n-vertex, m-edge graph. This is as fast as any known method methods seem to have a roughly quadratic growth rate. Received 30 August 1995; accepted 27 June 1996

for any graph density and faster on graphs of moderate density. The algorithm also admits efticient
distributed and parallel implementations. A parallel implementation running in O(n’log n) time using 1 Introduction Abstract
n processors and O(m) space is obtained. This time bound matches that of the Shiloach-Vishkin
algorithm, which also uses n processors but requires O(n’) space. The rnaximum flow problem is a classical combinatorial problem that comes up The maximum flow algorithm is distinguished by the long line of successive contributions researchers have made in
obtaining algorithms with incrementally better worst-case complexity. Some, but not all, of these theoretical improvements
in a wide variety of applications. In this paper we study implementations of the
have produced improvements in practice. The purpose of this paper is to test some of the major algorithmic ideas developed
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Non- push-rdabel [13, 17] method for the problem. in the recent years and to assess their utility on the empirical front. However, our study differs from previous studies in
75 The basic methods for the maximum flow problem include the network sim- 76
numerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph Theory-graph algorithms; plex method of Dantzig [6, 7], the augmenting path method of Ford and F~lker-
several ways. Whereas previous studies focus primarily on CPU time analysis, our analysis goes further and provides
detailed insight into algorithmic behavior. It not only observes how algorithms behave but also tries to explain why
network problems son [12], the blocking flow method of Dinitz [10], and the push-relabel method algorithms behave that way. We have limited our study to the best previous maximum flow algorithms and some of the
General Terms: Algorithms, Design, Theory, Verification of Goldberg and Tarjan [14, 17]. (An earlier algorithm of Cherkassky [5] has recent algorithms that are likely to be efficient in practice. Our study encompasses ten maximum flow algorithms and five
classes of networks. The augmenting path algorithms tested by us include Dinic's algorithm, the shortest augmenting path
many features of the push-relabel method.) The best theoretical time bounds
Additional Key Words and Phrases: Dynamic trees, maximum-flow problem for the maximum flow problem, based on the latter method, are as follows. An algorithm, and the capacity-scaling algorithm. The preflow-push algorithms tested by us include Karzanov's algorithm, three
implementations of Goldberg-Tarjan's algorithm, and three versions of Ahuja-Orlin-Tarjan's excess-scaling algorithms.
algorithm of Goldberg and Tarjan [17] runs in O(nm log(n2/m)) time, an algo-
 Maximum-flow algorithms: practice Maximum-flow algorithms: Matlab

Computer vision. Different algorithms work better for some dense

problems that arise in applications to computer vision.

In IEEE Transactions on PAMI, Vol. 26, No. 9, pp. 1124-1137, Sept. 2004 p.1

An Experimental Comparison of VERMA, BATRA: MAXFLOW REVISITED 1

Min-Cut/Max-Flow Algorithms for

Energy Minimization in Vision MaxFlow Revisited:
Yuri Boykov and Vladimir Kolmogorov∗ An Empirical Comparison of Maxflow
Algorithms for Dense Vision Problems
Abstract

After [15, 31, 19, 8, 25, 5] minimum cut/maximum flow algorithms on graphs emerged as Tanmay Verma IIIT-Delhi
an increasingly useful tool for exact or approximate energy minimization in low-level vision. [email protected] Delhi, India
The combinatorial optimization literature provides many min-cut/max-flow algorithms with
Dhruv Batra TTI-Chicago
[email protected] Chicago, USA
different polynomial time complexity. Their practical efficiency, however, has to date been

studied mainly outside the scope of computer vision. The goal of this paper is to provide an

experimental comparison of the efficiency of min-cut/max flow algorithms for applications

in vision. We compare the running times of several standard algorithms, as well as a

Abstract

new algorithm that we have recently developed. The algorithms we study include both Algorithms for finding the maximum amount of flow possible in a network (or max-
Goldberg-Tarjan style “push-relabel” methods and algorithms based on Ford-Fulkerson flow) play a central role in computer vision problems. We present an empirical compari-
son of different max-flow algorithms on modern problems. Our problem instances arise
style “augmenting paths”. We benchmark these algorithms on a number of typical graphs
from energy minimization problems in Object Category Segmentation, Image Deconvo-
in the contexts of image restoration, stereo, and segmentation. In many cases our new lution, Super Resolution, Texture Restoration, Character Completion and 3D Segmen-
algorithm works several times faster than any of the other methods making near real-time tation. We compare 14 different implementations and find that the most popularly used
implementation of Kolmogorov [5] is no longer the fastest algorithm available, especially
performance possible. An implementation of our max-flow/min-cut algorithm is available
for dense graphs.
upon request for research purposes.

Index Terms — Energy minimization, graph algorithms, minimum cut, maximum

flow, image restoration, segmentation, stereo, multi-camera scene reconstruction. 1 Introduction

∗
Yuri Boykov is with the Computer Science Department at the University of Western Ontario, Canada,
[email protected]. Vladimir Kolmogorov is with Microsoft Research, Cambridge, England, [email protected].
This work was mainly done while the authors were with Siemens Corp. Research, Princeton, NJ.
Over the past two decades, algorithms for finding the maximum amount of flow possible in
a network (or max-flow) have become the workhorses of modern computer vision and ma- 77 78
chine learning – from optimal (or provably-approximate) inference in sophisticated discrete
models [6, 11, 27, 30, 32] to enabling real-time image processing [38, 39].
Perhaps the most prominent role of max-flow is due to the work of Hammer [23] and
Kolmogorov and Zabih [27], who showed that a fairly large class of energy functions – sum
of submodular functions on pairs of boolean variables – can be efficiently and optimally
minimized via a reduction to max-flow. Max-flow also plays a crucial role in approximate
Maximum-flow algorithms: Google minimization of energy functions with multi-label variables [4, 6], triplet or higher order
terms [26, 27, 35, 37], global terms [30], and terms encoding label costs [11, 32].
Given the wide applicability, it is important to ask which max-flow algorithm should be
used. There are numerous algorithms for max-flow with different asymptotic complexities
and practical run-time behaviour. For an extensive list, we refer the reader to surveys in the
literature [2, 7]. Broadly speaking, there are three main families of max-flow algorithms:

1. Augmenting-Path (AP) variants: algorithms [5, 13, 14, 17, 21] that maintain a valid
flow during the algorithm, i.e. always satisfying the capacity and flow-conservation
constraints.
7. N ETWORK F LOW I
© 2012. The copyright of this document resides with its authors.
It may be distributed unchanged freely in print or electronic forms.

‣ max-flow and min-cut problems

‣ Ford–Fulkerson algorithm
‣ max-flow min-cut theorem
‣ capacity-scaling algorithm
‣ shortest augmenting paths
‣ Dinitz’ algorithm
‣ simple unit-capacity networks

79
Network flow: quiz 7 Simple unit-capacity networks

Which max-flow algorithm to use for bipartite matching? Def. A flow network is a simple unit-capacity network if:
・Every edge has capacity 1.
A. Ford–Fulkerson: O(m n C).
・Every node (other than s or t) has exactly one entering edge, node capacity = 1

or exactly one leaving edge, or both.

B. Capacity scaling: O(m2 log C).

C. Shortest augmenting path: O(m2 n). Property. Let G be a simple unit-capacity network and let f be a 0–1 flow.
Then, residual network G f is also a simple unit-capacity network.
D. Dinitz’ algorithm: O(m n2).

we’ll show that Dinitz’ algorithm runs Ex. Bipartite matching.

in O(m n1/2) time for bipartite matching 1
SIAM J. CoMavx.
Vol. 4, No. 4, December 1975

1 1
NETWORK FLOW AND TESTING GRAPH CONNECTIVITY*
SHIMON EVEN" AND R. ENDRE TARJAN:I:
Abstract. An algorithm of Dinic for finding the maximum flow in a network is described. It is
then shown that if the vertex capacities are all equal to one, the algorithm requires at most O(IV[ 1/2 IEI)
time, and if the edge capacities are all equal to one, the algorithm requires at most O(I VI 2/3. IEI) time.
Also, these bounds are tight for Dinic’s algorithm.
These results are used to test the vertex connectivity of a graph in O(IVI 1/z. IEI 2) time and the
edge connectivity in O(I V[ 5/3. IEI) time.

Key words. Dinic’s algorithm, maximum flow, connectivity, vertex connectivity, edge connec-
tivity 82
81
1. Network flow. Let G(V, E) be a finite directed graph, where V is the set of
vertices and E is the set of edges. Each edge e is assigned.a capacity c(e) O. >=
One of the vertices, s, is called the source, and another, t, is called the sink. We seek
a flow function f(e) on the edges such that for every e, c(e) f(e) >=
0 and such >=
that the total flow which enters a vertex, other than s or t, will equal the total
Simple unit-capacity networks
flow which leaves the vertex. Of all such flows, we want one for which the net total Simple unit-capacity networks
flow which emanates from s is maximum.
This well-known network flow problem [1] was recently reexamined. A
solution in O(n 5) steps, where n is the number of vertices, was produced by Edmonds within a phase, length of shortest
Shortest-augmenting-path
and Karp [2] in 1969.algorithm.
A solution in O(I VI 2" IE]) steps was published in Russian by Phase of normal augmentations. augmenting path does not change

・ Dinic [3] in 1970.

Normal augmentation:
In this section we length of shortest
present a solution path
in O(IVI 2. IEI), doesthenot
essentially samechange.
as ・Construct level graph LG.
・ Dinic’s. (This version was discovered independently by S. Even and J. Hopcroft.)
Special augmentation: length of shortest
The algorithm runs in phases, at most IVI path strictly
in number. We start with increases.
zero ・Start at s, advance along an edge in LG until reach t or get stuck.
flow; that is, f(e) 0 for every e E. In each phase, the flow is increased. New
phases are applied until no increase is possible. At that point, the proof of maxi- ・If reach t, augment flow; update LG; and restart from s.
mality is the same as that of Ford and Fulkerson [1], and it will not be repeated
Theorem. [Even–Tarjan 1975] In simple unit-capacity networks,
here. However, the algorithm up to that point is not a restriction of the freedom ・If get stuck, delete node from LG and go to previous node.
allowed by the Ford and Fulkerson algorithm--as is the case with
Dinitz’ algorithm computes a maximum flow in O(m n1/2the
and Karp algorithm. The computation within each phase is through a different
Edmonds
) time.
Pf. method of labeling and path finding.
Assume that we have a present flow f(e). An edge is usable in the forward construct level graph
・ Lemma 1.direction
Each iff(e)
phase < c(e),of
an edge may be usable in both directions.
the backward direction iff(e)
it is usable inaugmentations
andnormal > 0. Clearly,
takes O(m) time.
・ Each phase
1/2 starts with a breadth-first
Lemma 2. After n phases, val( f ) ≥ val( f ) – n . search from *s. That 1/2
is, we start
ing s with 0; i.e., 2(s) 0. Next, we label with all unlabeled vertices which are
by label-

・ Lemma 3.reachable
Afterfrom ≤ ns1/2viaadditional
a single usable edge, where the usable direction
augmentations, flow is from
is optimal.
s to ▪
Received by the editors June 27, 1974, and in revised form November 15, 1974.
-Computer Science Department, Technion-Israel Institute of Technology, Haifa, Israel. On
leave of absence from the Department of Applied Mathematics, Weizmann Institute of Science, Rehovot,
Israel. Parts1/2
s t
Lemma 3. After ≤ n additional augmentations, flow is optimal.
of this work were completed during the summers of 1972 and 1973 while he visited the
Department of Computer Science, Cornell University, Ithaca, New York.
Pf. Each augmentation increases flow value by at least 1. ▪
Computer Science Division, University of California at Berkeley, Berkeley, California 94720.
The work of this author was supported in part by the National Science Foundation under Grant
NSF-GJ-35604X, and by a Miller Research Fellowship.
507
Lemma 1 and Lemma 2. Ahead.
level graph LG

83 84
 Simple unit-capacity networks Simple unit-capacity networks

Phase of normal augmentations. Phase of normal augmentations.

・Construct level graph LG. ・Construct level graph LG.
・Start at s, advance along an edge in LG until reach t or get stuck. ・Start at s, advance along an edge in LG until reach t or get stuck.
・If reach t, augment flow; update LG; and restart from s. ・If reach t, augment flow; update LG; and restart from s.
・If get stuck, delete node from LG and go to previous node. ・If get stuck, delete node from LG and go to previous node.
remove from level graph
advance augment
all edges in augmenting path

s t s t

level graph LG level graph LG

85 86

Simple unit-capacity networks Simple unit-capacity networks

Phase of normal augmentations. Phase of normal augmentations.

・Construct level graph LG. ・Construct level graph LG.
・Start at s, advance along an edge in LG until reach t or get stuck. ・Start at s, advance along an edge in LG until reach t or get stuck.
・If reach t, augment flow; update LG; and restart from s. ・If reach t, augment flow; update LG; and restart from s.
・If get stuck, delete node from LG and go to previous node. ・If get stuck, delete node from LG and go to previous node.

advance retreat

s t s t

level graph LG level graph LG

87 88
 Simple unit-capacity networks Simple unit-capacity networks

Phase of normal augmentations. Phase of normal augmentations.

・Construct level graph LG. ・Construct level graph LG.
・Start at s, advance along an edge in LG until reach t or get stuck. ・Start at s, advance along an edge in LG until reach t or get stuck.
・If reach t, augment flow; update LG; and restart from s. ・If reach t, augment flow; update LG; and restart from s.
・If get stuck, delete node from LG and go to previous node. ・If get stuck, delete node from LG and go to previous node.

advance augment

s t s t

level graph LG level graph LG

89 90

Simple unit-capacity networks Simple unit-capacity networks: analysis

Phase of normal augmentations. Phase of normal augmentations.

・Construct level graph LG. ・Construct level graph LG.
・Start at s, advance along an edge in LG until reach t or get stuck. ・Start at s, advance along an edge in LG until reach t or get stuck.
・If reach t, augment flow; update LG; and restart from s. ・If reach t, augment flow; update LG; and restart from s.
・If get stuck, delete node from LG and go to previous node. ・If get stuck, delete node from LG and go to previous node.
Lemma 1. A phase of normal augmentations takes O(m) time.
end of phase (length of shortest augmenting path has increased)
Pf.
・O(m) to create level graph LG.
・O(1) per edge (each edge involved in at most one advance, retreat, and
augmentation).
s t
・O(1) per node (each node deleted at most once). ▪

level graph LG

91 92
 Network flow: quiz 8 Simple unit-capacity networks: analysis

Consider running advance–retreat algorithm in a unit-capacity network Lemma 2. After n1/2 phases, val( f ) ≥ val( f *) – n1/2.
(but not necessarily a simple one). What is running time? ・After n1/2 phases, length of shortest augmenting path is > n1/2.
both indegree and outdegree ・Thus, level graph has ≥ n1/2 levels (not including levels for s or t).
・Let 1 ≤ h ≤ n1/2 be a level with min number of nodes ⇒ ⎢Vh ⎢ ≤ n1/2.
of a node can be larger than 1

A. O(m). useful for this

week’s homework!

B. O(m3/2).

C. O(m n).
level graph LG for flow f
D. May not terminate.

s t

V1 Vh Vn1/2
94
93

Simple unit-capacity networks: analysis Simple unit-capacity networks: review

Lemma 2. After n1/2 phases, val( f ) ≥ val( f *) – n1/2. Theorem. [Even–Tarjan 1975] In simple unit-capacity networks,
・After n1/2 phases, length of shortest augmenting path is > n1/2. Dinitz’ algorithm computes a maximum flow in O(m n1/2) time.
・Thus, level graph has ≥ n1/2 levels (not including levels for s or t). Pf.
・Let 1 ≤ h ≤ n1/2 be a level with min number of nodes ⇒ ⎢Vh ⎢ ≤ n1/2. ・Lemma 1. Each phase takes O(m) time.
・Let A = {v : ℓ(v) < h} ∪ {v : ℓ(v) = h and v has ≤ 1 outgoing residual edge}. ・Lemma 2. After n1/2 phases, val( f ) ≥ val( f *) – n1/2.
・capf (A, B) ≤ ⎢Vh ⎢ ≤ n1/2 ⇒ val( f ) ≥ val( f *) – n1/2. ▪ ・Lemma 3. After ≤ n1/2 additional augmentations, flow is optimal. ▪
unit-capacity
simple network
residual network Gf Corollary. Dinitz’ algorithm computes max-cardinality bipartite matching
residual edges
in O(m n1/2) time.
A

s t

V1 Vh Vn1/2
95 96