程序代写代做代考 go C algorithm data structure graph discrete mathematics 7. NETWORK FLOW I

7. NETWORK FLOW I
‣ 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
Lecture slides by Kevin Wayne  Copyright © 2005 Pearson-Addison Wesley 
http://www.cs.princeton.edu/~wayne/kleinberg-tardos
Last updated on 1/14/20 2:18 PM

SECTION 7.1
7. NETWORK FLOW I
‣ 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

Flow network
A・flow network is a tuple G = (V, E, s, t, c). ・Digraph (V, E) with source s ∈ V and sink t ∈ V.
Capacity c(e) ≥ 0 for each e ∈ E.
Intuition. Material flowing through a transportation network;
material originates at source and is sent to sink.
capacity
assume all nodes are reachable from s
10
9
4 15
15 10
10t
15 10
s5 8
15
4 6
16
3

Minimum-cut problem
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.
cap(A,B)= c(e) e 􏰑􏰜􏰗 􏰑􏰏 A
10
s5t 15
capacity = 10 + 5 + 15 = 30
4

Network flow: quiz 1
Which is the capacity of the given st-cut?
A. 11 (20 + 25 − 8 − 11 − 9 − 6)
B. 34 (8 + 11 + 9 + 6)
C. 45 (20 + 25)
D. 79
(20 + 25 + 8 + 11 + 9 + 6)
s
capacity
20 8 10
6898
1 16 25 t
7
6
12
11

Maximum-flow problem
D・ef. An st-flow (flow) f is a function that satisfies:
・For each e ∈ E: 0 f(e) c(e) [capacity]
=
e 􏰑􏰜􏰗 􏰑􏰏 v
capacity
For each v ∈ V – {s, t}:
e 􏰎􏰐 􏰗􏰑 v
f(e)
f(e)
[flow conservation]
flow
5 /9
inflow at v = 5 + 5 + 0 outflow at v = 10 + 0
= 10 = 10
s 5 / 5
5 / 8
10 / 10 t
0 /4
0 / 15
v
0 / 15
0 /4
10 / 16
8
5 / 10
5 / 15
10 / 10
10 / 15
0/ 6
10 / 10

Maximum-flow problem
Def. An st-flow (flow) f is a function that satisfies:
・For each e ∈ E: ・For each v ∈ V – {s, t}:
Def. The value of a flow f
0 f(e) c(e)
[capacity]
[flow conservation]
f(e) e 􏰎􏰐 􏰗􏰑 s
f(e) e 􏰎􏰐 􏰗􏰑 v
= f(e) e 􏰑􏰜􏰗 􏰑􏰏 v
is:
val(f)
=
f(e) e 􏰑􏰜􏰗 􏰑􏰏 s
5 /9
0 /4
0 / 15
s
5 / 5
5 / 8
10 / 10
t
value
= 5 + 10 + 10 = 25
0 /4
0 / 15
10 / 16
9
5 / 10
5 / 15
10 / 10
10 / 15
0/ 6
10 / 10

Maximum-flow problem
Def. An st-flow (flow) f is a function that satisfies:
・For each e ∈ E: ・For each v ∈ V – {s, t}:
0 f(e) c(e)
[capacity]
[flow conservation]
f(e) e 􏰎􏰐 􏰗􏰑 s
Def. The value of a flow f is: val(f)
Max-flow problem. Find a flow of maximum value.
f(e) e 􏰎􏰐 􏰗􏰑 v
= f(e) e 􏰑􏰜􏰗 􏰑􏰏 v
= f(e) e 􏰑􏰜􏰗 􏰑􏰏 s
8 /9
0 /4
0 / 15
s
5 / 5
8 / 8
10 / 10
t
value
= 10 + 5 + 13 = 28
0 /4
0 / 15
13 / 16
10
8 / 10
2 / 15
10 / 10
13 / 15
3/ 6
10 / 10

Toward a max-flow algorithm
Greedy algorithm.
・Start with f (e) = 0 for each edge e ∈ E.
・Find an s↝t path P where each edge has f (e) < c(e). ・Augment flow along path P. ・Repeat until you get stuck. flow network G and flow f flow capacity 0 /4 0 / 2 0/ 6 s 0 / 10 0 / 9 0 / 10 t value of flow 0 12 0 / 10 0 /8 0 / 10 Toward a max-flow algorithm Greedy algorithm. ・Start with f (e) = 0 for each edge e ∈ E. ・Find an s↝t path P where each edge has f (e) < c(e). ・Augment flow along path P. ・Repeat until you get stuck. flow network G and flow f 0 /4 0 / 2 0/ 6 s 0 / 10 0 / 9 0 / 10 t 0 13 0 / 10 0 /8 0 / 10 Toward a max-flow algorithm Greedy algorithm. ・Start with f (e) = 0 for each edge e ∈ E. ・Find an s↝t path P where each edge has f (e) < c(e). ・Augment flow along path P. ・Repeat until you get stuck. flow network G and flow f 0 /4 0 / 2 0/ 6 s 0 / 10 0 / 9 8 —0 / 10 t 0 + 8 = 8 14 0 / 10 8 —0 / 8 8 —0 / 10 Toward a max-flow algorithm Greedy algorithm. ・Start with f (e) = 0 for each edge e ∈ E. ・Find an s↝t path P where each edge has f (e) < c(e). ・Augment flow along path P. ・Repeat until you get stuck. flow network G and flow f 0 /4 s 0 / 10 2 10 —0 / 9 —8 / 10 t 8 + 2 = 10 2 —0 / 2 0 / 6 15 0 / 10 8 /8 10 — 8 / 10 Toward a max-flow algorithm Greedy algorithm. ・Start with f (e) = 0 for each edge e ∈ E. ・Find an s↝t path P where each edge has f (e) < c(e). ・Augment flow along path P. ・Repeat until you get stuck. flow network G and flow f 2 / 2 0 /4 68 s —0 / 10 —2 / 9 10 / 10 t 10 + 6 = 16 16 6 —0 / 6 6 — 0 / 10 8 /8 10 / 10 Toward a max-flow algorithm Greedy algorithm. ・Start with f (e) = 0 for each edge e ∈ E. ・Find an s↝t path P where each edge has f (e) < c(e). ・Augment flow along path P. ・Repeat until you get stuck. flow network G and flow f ending flow value = 16 0 /4 2 / 2 6/ 6 s 6 / 10 8 / 9 10 / 10 t 16 17 6 / 10 8 /8 10 / 10 Toward a max-flow algorithm Greedy algorithm. ・Start with f (e) = 0 for each edge e ∈ E. ・Find an s↝t path P where each edge has f (e) < c(e). ・Augment flow along path P. ・Repeat until you get stuck. flow network G and flow f but max-flow value = 19 3 /4 0 / 2 6/ 6 s 9 / 10 9 / 9 10 / 10 t 19 18 9 / 10 7 /8 10 / 10 Why the greedy algorithm fails Q. Why does the greedy algorithm fail? A. Once greedy algorithm increases flow on an edge, it never decreases it. E・x. Consider flow network G . ・The unique max flow f * has f *(v, w) = 0. Greedy algorithm could choose s→v→w→t as first path. flow network G v2t 212 s2w Bottom line. Need some mechanism to “undo” a bad decision. 19 Residual network Original edge. e = (u, v) ∈ E. ・Flow f (e). ・Capacity c(e). Reverse edge. ereverse = (v, u). ・“Undo” flow sent. Residual capacity. original flow network G u 6/17 v flow residual network Gf capacity residual capacity u11v cf(e)= c(e)f(e) 􏰎􏰏eE 6 f(e) 􏰎􏰏 e􏰖􏰌􏰝􏰌􏰖􏰍􏰌 E R・esidual network. Gf = (V, Ef , s, t, cf ). reverse ・Ef = {e : f (e) < c(e)} ∪ {e : f (e) > 0}. corresponding forward edge
Key property: f ʹ is a flow in G iff f + f ʹ is a flow in G. f
edges with positive residual capacity
reverse edge
where flow on a reverse edge negates flow on
20

Augmenting path
Def. An augmenting path is a simple s↝t path in the residual network Gf . Def. The bottleneck capacity of an augmenting path P is the minimum
residual capacity of any edge in P.
Key property. Let f be a flow and let P be an augmenting path in Gf . Then, after calling f ʹ ← AUGMENT( f, c, P), the resulting f ʹ is a flow and val( f ʹ) = val( f ) + bottleneck(Gf, P).
AUGMENT( f, c, P) ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
δ ← bottleneck capacity of augmenting path P. FOREACH edge e ∈ P :
IF (e∈E) f(e) ← f(e) + δ.
ELSE f(ereverse)←f(ereverse) – δ.
RETURN f. ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
21

Network flow: quiz 2
Which is the augmenting path of highest bottleneck capacity?
A. A→F→G→H
B. A→B→C→D→H
C. A→F→B→G→H
D. A→F→B→G→C→D→H
source
residual capacity
5
A 9 B 8 C 6 D
584585
E 5 F 2 G 3 H
5 target
22
6
7
7

Ford–Fulkerson algorithm
Ford–Fulkerson augmenting path algorithm.
・Start with f (e) = 0 for each edge e ∈ E.
・Find an s↝t path P in the residual network G .
・Augment flow along path P. ・Repeat until you get stuck.
f
FORD–FULKERSON(G) ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
FOREACH edgee∈E: f(e)←0.
Gf ← residual network of G with respect to flow f.
WHILE (there exists an s↝t path P in Gf ) f ← AUGMENT( f, c, P).
Update Gf. RETURN f.
augmenting path
23

SECTION 7.2
7. NETWORK FLOW I
‣ 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

Relationship between flows and cuts
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).
val(f) = f(e) f(e) e 􏰑􏰜􏰗 􏰑􏰏 A e 􏰎􏰐 􏰗􏰑 A
netflowacrosscut = 5+10+10= 25
5 /9
0 /4
0 / 15
s 5 / 5
5 / 8
10 / 10 t
value of flow = 25
0 /4
0 / 15
10 / 16
25
5 / 10
5 / 15
10 / 10
10 / 15
0/ 6
10 / 10

Relationship between flows and cuts
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).
val(f) = f(e) f(e) e 􏰑􏰜􏰗 􏰑􏰏 A e 􏰎􏰐 􏰗􏰑 A
netflowacrosscut = 10+5+10= 25
5 /9
0 /4
0 / 15
s 5 / 5
5 / 8
10 / 10 t
value of flow = 25
0 /4
0 / 15
10 / 16
26
5 / 10
5 / 15
10 / 10
10 / 15
0/ 6
10 / 10

Relationship between flows and cuts
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).
val(f) = f(e) f(e) e 􏰑􏰜􏰗 􏰑􏰏 A e 􏰎􏰐 􏰗􏰑 A
netflowacrosscut = (10+10 +5+10+0+0)–(5+5+0+0) = 25
5 /9
0 /4
0 / 15
edges from B to A
t value of flow = 25
s 5 / 5
5 / 8
10 / 10
0 /4
0 / 15
10 / 16
27
5 / 10
5 / 15
10 / 10
10 / 15
0/ 6
10 / 10

Network flow: quiz 3
Which is the net flow across the given cut?
A. 11 (20 + 25 − 8 − 11 − 9 − 6)
B. 26 (20 + 22 − 8 − 4 − 4)
C. 42 (20 + 22)
D. 45 (20 + 25)
s
1 / 6
20 / 20
flow capacity 8 / 8
4/ 9
4 / 10
8 / 8
4/ 8
t
1 / 1
14 / 16
22 / 25
28
5 / 12
4 / 11
0 /6

Relationship between flows and cuts
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).
Pf.
val(f) = f(e) f(e) e 􏰑􏰜􏰗 􏰑􏰏 A e 􏰎􏰐 􏰗􏰑 A
val(f) = f(e) f(e) e 􏰑􏰜􏰗 􏰑􏰏 s e 􏰎􏰐 􏰗􏰑 s
by flow conservation, all terms except for v = s are 0
= f(e) f(e) vA e 􏰑􏰜􏰗 􏰑􏰏 v e 􏰎􏰐 􏰗􏰑 v
val(f) = f(e) f(e) e 􏰑􏰜􏰗 􏰑􏰏 A e 􏰎􏰐 􏰗􏰑 A
▪
29

Relationship between flows and cuts
Weak duality. Let f be any flow and (A, B) be any cut. Then, val( f ) ≤ cap(A, B).
Pf.
flow value lemma
f(e)
e 􏰑 􏰜 􏰗 􏰑 􏰏 A e 􏰑􏰜􏰗 􏰑􏰏 A
▪
10 9 / 10 t s 5
15
v a l ( f ) = f ( e ) f ( e ) e 􏰑􏰜􏰗 􏰑􏰏 A e 􏰎􏰐 􏰗􏰑 A

= cap(A,B) 8 /9
c(e)
s 5 / 5
0 / 4
0 / 4
7 / 8
12 / 16
0 / 15
0 / 15
t
value of flow = 27
≤
capacity of cut = 30
30
8 / 10
2 / 15
10 / 10
12 / 15
2/ 6
10 / 10

Certificate of optimality
Corollary. Let f be a flow and let (A, B) be any cut.
If val( f ) = cap(A, B), then f is a max flow and (A, B) is a min cut.
weak duality
P・f.
・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
0 / 4
0 / 15
10
s 5 / 5 8 / 8 10 / 10 t s 8 t
0 / 4 0 / 15
13 / 16
10
value of flow = 28
= capacity of cut = 28
31
8 / 10
2 / 15
10 / 10
13 / 15
3/ 6
10 / 10

Max-flow min-cut theorem
Max-flow min-cut theorem. Value of a max flow = capacity of a min cut. strong duality
1956 IRE TRANXACTIONX ON INFORiMATION THEORY 117 A Note on the Maximum Flow Through a Network*
P. ELIASt, A. FEINSTEINI,
Summary–This note discusses the problem of maximizing the rate of flow from one terminal to another, through a network which consists of a number of branches, each of which has a !imited capa- city. The main result is a theorem: The maximum possible flow from left to right through a network is equal to the minimum value among 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 nodes are used.
AND C. E. SHANNON!
from one terminal to the other in the original network passes through at least one branch in the cut-set. In the network above, some examples of cut-sets are (d, e, f), and (b,c,e,g,h), (d,g,h,i).By asimple cut-setwewill mean a cut-set such that if any branch is omitted it is no 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 deleted from a connected two-terminal network, the net- work falls into exactly two parts, a left part containing the left terminal and a right part containing the right terminal. We assign a value to a simple cut-set by taking the sum of capacities of branches in the cut-set, only counting
c
ONSIDER a two-terminal network such as that of Fig. 1. The branches of the network might represent communication channels, or, more
32
generally, any conveying system of limited capacity as, for example, a railroad system, a power feeding system,

Max-flow min-cut theorem
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.
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 ).
ii. f is a max flow.
iii. There is no augmenting path with respect to f.
[・i⇒ii]
This is the weak duality corollary. ▪
if Ford–Fulkerson terminates, then f is max flow
33

Max-flow min-cut theorem
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.
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 ).
ii. f is a max flow.
iii. There is no augmenting path with respect to f.
[ ii ⇒ iii ] We prove contrapositive: ¬ iii ⇒ ¬ ii.
・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. ▪
34

Max-flow min-cut theorem
[ iii ⇒ i ]
・Let f be a flow with no augmenting paths.
・Let A = set of nodes reachable from s in residual network Gf.
・By definition of A: s ∈ A.
・By definition of flow f: t ∉ A. edge e = (v, w) with v ∈ B, w ∈ A must have f(e) = 0
val(f) = f(e) f(e) e 􏰑􏰜􏰗 􏰑􏰏 A e 􏰎􏰐 􏰗􏰑 A
= c(e) 0 e 􏰑􏰑􏰜􏰜􏰗􏰗 􏰑􏰑􏰏􏰏 A
= cap(A,B)
original flow network G
A
B
t
flow value lemma
s
edge e = (v, w) with v ∈ A, w ∈ B must have f(e) = c(e)
35

Computing a minimum cut from a maximum flow
Theorem. Given any max flow f , can compute a min cut (A, B) in O(m) time. Pf. Let A = set of nodes reachable from s in residual network G f . ▪
argument from previous slide implies that capacity of (A, B) = value of flow f
8 1
4
As5 810t 15
15
31
16
36
10
8 2
13 2
10
6
2 13

SECTION 7.3
7. NETWORK FLOW I
‣ 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

Analysis of Ford–Fulkerson algorithm (when capacities are integral)
Assumption. Every edge capacity c(e) is an integer between 1 and C.
Integrality invariant. Throughout Ford–Fulkerson, every edge flow f (e)
and residual capacity cf (e) is an integer.
Pf. By induction on the number of augmenting paths. ▪ consider cut A = { s } (assumes no parallel edges)
Theorem. Ford–Fulkerson terminates after at most val( f *) ≤ n C augmenting paths, where f * is a max flow.
Pf. Each augmentation increases the value of the flow by at least 1. ▪
Corollary. The running time of Ford–Fulkerson is O(m n C).
Pf. Can use either BFS or DFS to find an augmenting path in O(m) time. ▪
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
Q. Is generic Ford–Fulkerson algorithm poly-time in input size? m, n, and log C
A. No. If max capacity is C, then algorithm can take ≥ C iterations. ・s→v→w→t
・s→w→v→t ・s→v→w→t ・s→w→v→t ・… ・s→v→w→t ・s→w→v→t
each augmenting path sends only 1 unit of flow (# augmenting paths = 2C)
s
v1w
t
39
C
C
C
C

Network flow: quiz 4
The Ford–Fulkerson algorithm is guaranteed to terminate if the edge capacities are …
A. Rational numbers.
B. Real numbers.
C. Both A and B.
D. Neither A nor B.
Let D denote the product (or lcm) of the denominators.
Then, every edge flow f (e) and every residual capacity cf (e) is a multiple of 1 / D.
40

Choosing good augmenting paths
Use care when selecting augmenting paths.
・Some choices lead to exponential algorithms. ・Clever choices lead to polynomial algorithms.
Pathology. When edge capacities can be irrational, no guarantee that Ford–Fulkerson terminates (or converges to a maximum flow)!
Goal. Choose augmenting paths so that: ・Can find augmenting paths efficiently. ・Few iterations.
41

Choosing good augmenting paths
C・hoose augmenting paths with:
・Max bottleneck capacity (“fattest”).
how to find? next
・Sufficiently large bottleneck capacity.
Fewest edges.
Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
JACK EDMONDS
University of Waterloo, Waterloo, Ontario, Canada
AND
RICHARD M. KARP
University of California, Berkeley, California
ABSTRACT. This paper presents new algorithms for the maximum flow problem, the Hitchcock transportation problem, and the general minimum-cost flow problem. Upper bounds on the numbers of steps in these algorithms are derived, and are shown to compale favorably with upper bounds on the numbers of steps required by earlier algorithms.
First, the paper states the maximum flow problem, gives the Ford-Fulkerson labeling method
for its solution, and points out that an improper choice of flow augmenting paths can lead to
Edmonds-Karp 1972 (USA)
Dinitz 1970 (Soviet Union)
invented in response to a class exercises by Adel’son-Vel’skiĭ
severe computational difficulties. Then rules of choice that avoid these difficulties are given.
We show that, if each flow augmentation is made along an augmenting path having a minimum number of arcs, then a maximum flow in an n-node network will be obtained after no more than ~(na – n) augmentations; and then we show that if each flow change is chosen to produce a maximum increase in the flow value then, provided the capacities are integral, a maximum flow will be determined within at most 1 + logM/(M–1) if(t, S) augmentations, wheref*(t, s) is the value of the maximum flow and M is the maximum number of arcs across a cut.
Next a new algorithm is given for the minimum-cost flow problem, in which all shortest-path computations are performed on networks with all weights nonnegative. In particular, this algorithm solves the n X n assigmnent problem in O(n3)steps. Following that we explore a “scaling” technique for solving a minimum-cost flow problem by treating a sequence of derived problems with “scaled down” capacities. It is shown that, using this technique, the solution of a Iiitchcock transportation problem with m sources and n sinks, m ~ n, and maximum flow B, requires at most (n + 2) log2 (B/n) flow augmentations. Similar results are also given for the general minimum-cost flow problem.
42
ahead
An abstract stating the main results of the present paper was presented at the Calgary
International Conference on Combinatorial Structures and Their Applications, June 1969.

Capacity-scaling algorithm
O・verview. Choosing augmenting paths with “large” bottleneck capacity.
・Maintain scaling parameter Δ.
Let Gf (Δ) be the part of the residual network containing
・only those edges with capacity ≥ Δ.
Any augmenting path in Gf (Δ) has bottleneck capacity ≥ Δ.
ss
though not necessarily largest
1
tt
Gf Gf(Δ), Δ=100
43
110
170
110
170
102
122
102
122

Capacity-scaling algorithm
CAPACITY-SCALING(G) __________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
FOREACH edgee∈E: f(e)←0. Δ ← largest power of 2 ≤ C.
WHILE (Δ ≥ 1)
Gf (Δ) ← Δ-residual network of G with respect to flow f .
WHILE (there exists an s↝t path P in Gf (Δ)) f ← AUGMENT( f, c, P).
Update Gf (Δ).
Δ ← Δ / 2.
Δ-scaling phase
RETURN f. __________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
44

Capacity-scaling algorithm: proof of correctness
Assumption. All edge capacities are integers between 1 and C. Invariant. The scaling parameter Δ is a power of 2.
Pf. Initially a power of 2; each phase divides Δ by exactly 2. ▪
Integrality invariant. Throughout the algorithm, every edge flow f (e) and residual capacity cf (e) is an integer.
Pf. Same as for generic Ford–Fulkerson. ▪
Theorem. If capacity-scaling algorithm terminates, then f is a max flow. Pf.
・By integrality invariant, when Δ = 1 ⇒ Gf (Δ) = Gf .
・Upon termination of Δ = 1 phase, there are no augmenting paths. ・Result follows augmenting path theorem ▪
45

Capacity-scaling algorithm: analysis of running time
Lemma 1. There are 1 + ⎣log2 C⎦ scaling phases.
Pf. Initially C / 2 < Δ ≤ C; Δ decreases by a factor of 2 in each iteration. ▪ Lemma 2. Let f be the flow at the end of a Δ-scaling phase. Then, the max-flow value ≤ val( f ) + m Δ. Pf. Next slide. Lemma 3. There are ≤ 2m augmentations per scaling phase. Pf. ・Let f be the flow at the beginning of a Δ-scaling phase. ・ or equivalently, at the end of a 2Δ-scaling phase ・Lemma 2 ⇒ max-flow value ≤ val(f) + m (2 Δ). Each augmentation in a Δ-phase increases val( f ) by at least Δ. ▪ Theorem. The capacity-scaling algorithm takes O(m2 log C) time. P・f. ・Lemma 1 + Lemma 3 ⇒ O(m log C) augmentations. 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 Δ. Pf. ・We show there exists a cut (A, B) such that cap(A, B) ≤ val(f) + m Δ. ・Choose A to be the set of nodes reachable from s in Gf (Δ). ・By definition of A: s ∈ A. ・By definition of flow f: t ∉ A. edge e = (v, w) with v ∈ B, w ∈ A val(f) = f(e) f(e) e 􏰑􏰜􏰗 􏰑􏰏 A e 􏰎􏰐 􏰗􏰑 A original flow network A must have f(e) < Δ B flow value lemma (c(e) ) e 􏰑􏰑􏰜􏰜􏰗􏰗 􏰑􏰑􏰏􏰏 A e 􏰎􏰎􏰐􏰐 􏰗􏰗􏰑􏰑 A t c(e) e 􏰑􏰜􏰗 􏰑􏰏 A e 􏰑􏰜􏰗 􏰑􏰏 A e 􏰎􏰐 􏰗􏰑 A s cap(A,B) m edge e = (v, w) with v ∈ A, w ∈ B must have f(e) > c(e) – Δ
47

SECTION 17.2
7. NETWORK FLOW I
‣ 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

Shortest augmenting path
Q. How to choose next augmenting path in Ford–Fulkerson? A. Pick one that uses the fewest edges.
can find via BFS
SHORTEST-AUGMENTING-PATH(G) _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
FOREACH e∈E: f(e)←0.
Gf ← residual network of G with respect to flow f.
WHILE (there exists an s↝t path in Gf ) P ← BREADTH-FIRST-SEARCH(Gf ).
f ←AUGMENT(f,c,P).
Update Gf.
RETURN f. _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
49

Shortest augmenting path: overview of analysis
Lemma 1. The length of a shortest augmenting path never decreases. Pf. Ahead.
number of edges
Lemma 2. After at most m shortest-path augmentations, the length of a shortest augmenting path strictly increases.
Pf. Ahead.
Theorem. The shortest-augmenting-path algorithm takes O(m2 n) time. P・f.
・O(m) time to find a shortest augmenting path via BFS. There are ≤ m n augmentations.
– –
at most m augmenting paths of length k at most n−1 different lengths ▪
augmenting paths are simple paths
Lemma 1 + Lemma 2
50

Shortest augmenting path: analysis
Def. Given a digraph G = (V, E) with source s, its level graph is defined by:
・l(v) = number of edges in shortest s↝v path.
・L = (V, E ) is the subgraph of G that contains only those edges (v, w) ∈ E GG
with l(w) = l(v) + 1. graph G
st
level graph LG
st
l=0 l=1 l=2 l=3
51

Network flow: quiz 5
Which edges are in the level graph of the following digraph? 
A. D→F. B. E→F.
C. D.
Both A and B. Neither A nor B.
13
BD
source
F sink 0123
52
A
C E

Shortest augmenting path: analysis
L・emma 1. The length of a shortest augmenting path never decreases.
・Let f and f ʹ be flow before and after a shortest-path augmentation.
・Let L and L ʹ be level graphs of G and G ʹ . GG ff
Only back edges added to Gf ′
(any s↝t path that uses a back edge is longer than previous length) ▪
level graph LG
st
l=0 l=1 l=2 l=3 level graph LG′
st
54

Shortest augmenting path: analysis
Lemma 2. After at most m shortest-path augmentations, the length of a shortest augmenting path strictly increases.
・At least one (bottleneck) edge is deleted from LG per augmentation.
No new edge added to L until shortest path length strictly increases. ▪
level graph LG
st
l=0 l=1 l=2 l=3 level graph LG′
G
st
55

Shortest augmenting path: review of analysis
Lemma 1. Throughout the algorithm, the length of a shortest augmenting path never decreases.
Lemma 2. After at most m shortest-path augmentations, the length of a shortest augmenting path strictly increases.
Theorem. The shortest-augmenting-path algorithm takes O(m2 n) time.
56

Shortest augmenting path: improving the running time
Note. Θ(m n) augmentations necessary for some flow networks. ・Try to decrease time per augmentation instead.
・Simple idea ⇒ O(mn2 ) [Dinitz 1970] ・Dynamic trees ⇒ O(m n log n) [Sleator–Tarjan 1983]
JOURNAL OF COMPUTER AND SYSTEM SCIENCES 26, 362-391 (1983)
ahead
A Data Structure for Dynamic Trees
DANIEL D. SLEATOR AND ROBERT ENDRE TARJAN
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 sequence of two kinds of operations: a link operation that combines two trees into one by adding an edge, and a cut operation that divides one tree into two by deleting an edge. Each operation requires O(log n) time. Using this data structure, new fast algorithms are obtained for the following problems:
(1) Computing
(2) Solving
nearest common
various network flows.
flows, and
(3) Computing
acyclic
certain kinds (4) Implementing the network
spanning minimum-cost
trees. flows.
ancestors.
flow problems including
of constrained minimum simplex algorithm for
finding maximum flows, blocking
The
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.
most significant application is (2); an O(mn log n)-time algorithm is obtained to find a
1. INTR~DIJCTI~N 57
In this paper we consider the following problem: We are given a collection of

SECTION 18.1
7. NETWORK FLOW I
‣ 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

Dinitz’ algorithm
Two types of augmentations.
・Normal: length of shortest path does not change. ・Special: length of shortest path strictly increases.
within a phase, length of shortest augmenting path does not change
・Start at s, advance along an edge in LG until reach t or get stuck. ・If reach t, augment flow; update L ; and restart from s.
If get stuck, delete node from L and retreat to previous node. G
construct level graph
P・hase of normal augmentations. ・Construct level graph L .
G
G
st
level graph LG
59

Dinitz’ algorithm
Two types of augmentations.
・Normal: length of shortest path does not change. ・Special: length of shortest path strictly increases.
Phase of normal augmentations.
・Construct level graph LG.
・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 get stuck, delete node from LG and retreat to previous node.
advance
s
t
level graph LG
60

Dinitz’ algorithm
Two types of augmentations.
・Normal: length of shortest path does not change. ・Special: length of shortest path strictly increases.
Phase of normal augmentations.
・Construct level graph LG.
・Start at s, advance along an edge in LG until reach t or get stuck.
・If reach t, augment flow; update L ; and restart from s. G
If get stuck, delete node from L and retreat to previous node. G
augment
remove from level graph edges with bottleneck capacity
st
level graph LG
61

Dinitz’ algorithm (as refined by Even and Itai)
ADVANCE(v) ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
IF (v=t)
AUGMENT(P).
Remove saturated edges from LG. P ←∅.
GOTO ADVANCE(s).
IF
(there exists edge (v, w) ∈ LG) Add edge (v, w) to P.
GOTO ADVANCE(w).
ELSE
GOTO RETREAT(v). ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
INITIALIZE(G, f ) _______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
LG ← level-graph of Gf. P ←∅.
GOTO ADVANCE(s). _______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
RETREAT(v) _______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
IF (v=s) STOP.
ELSE
Delete v (and all incident edges) from LG.
Remove last edge (u, v) from P.
GOTO ADVANCE(u). _______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
70

Network flow: quiz 6
How to compute the level graph LG efficiently?
A. B. C. D.
Depth-first search. Breadth-first search. Both A and B. Neither A nor B.
13
BD
source
F sink 0123
71
A
C E

Dinitz’ algorithm: analysis
Lemma. A phase can be implemented to run in O(m n) time. Pf.
・Initialization happens once per phase. O(m) using BFS ・At most m augmentations per phase. O(mn) per phase
(because an augmentation deletes at least one edge from LG) ・At most n retreats per phase. O(m + n) per phase ・(because a retreat deletes one node from LG)
At most mn advances per phase. O(mn) per phase (because at most n advances before retreat or augmentation) ▪
Theorem. [Dinitz 1970] Dinitz’ algorithm runs in O(mn2) time. P・f.
・By Lemma, O(mn) time per phase.
At most n−1 phases (as in shortest-augmenting-path analysis). ▪
72

Augmenting-path algorithms: summary
year
method
# augmentations
running time
1955
augmenting path
nC
O(m n C)
1972
fattest path
m log (mC)
O(m2 log n log (mC))
1972
capacity scaling
m log C
O(m2 log C)
1985
improved capacity scaling
m log C
O(m n log C)
1970
shortest augmenting path
mn
O(m2 n)
1970
level graph
mn
O(m n2 )
1983
dynamic trees
mn
O(mn log n)
fat paths
shortest paths
augmenting-path algorithms with m edges, n nodes, and integer capacities between 1 and C
73

Maximum-flow algorithms: theory highlights
year
method
worst case
discovered by
1951
simplex
O(m n2 C)
Dantzig
1955
augmenting paths
O(m n C)
Ford–Fulkerson
1970
shortest augmenting paths
O(m n2)
Edmonds–Karp, Dinitz
1974
blocking flows
O(n3)
Karzanov
1983
dynamic trees
O(m n log n)
Sleator–Tarjan
1985
improved capacity scaling
O(m n log C)
Gabow
1988
push–relabel
O(m n log (n2 / m))
Goldberg–Tarjan
1998
binary blocking flows
O(m3/2 log (n2 / m) log C)
Goldberg–Rao
2013
compact networks
O(m n)
Orlin
2014
interior-point methods
Õ(m n1/2 log C)
Lee–Sidford
2016
electrical flows
Õ(m10/7 C1/7)
Mądry
20xx
max-flow algorithms with m edges, n nodes, and integer capacities between 1 and C 74

Maximum-flow algorithms: practice
Push–relabel algorithm (SECTION 7.4). [Goldberg–Tarjan 1988]
Increases flow one edge at a time instead of one augmenting path at a time.
A New Approach to the Maximum-Flow Problem
ANDREW V. GOLDBERG
Massachusetts Institute of Technology, Cambridge, Massachusetts
AND
ROBERT E. TARJAN
Princeton University, Princeton, New Jersey, and AT&T Bell Laboratories, Murray Hill, New Jersey
Abstract. All previously known efftcient maximum-flow algorithms work by finding augmenting paths, either one path at a time (as in the original Ford and Fulkerson algorithm) or all shortest-length augmenting paths at once (using the layered network approach of Dinic). An alternative method based on the preflow concept of Karzanov is introduced. A preflow is like a flow, except that the total amount flowing into a vertex is allowed to exceed the total amount flowing out. The method maintains a preflow in the original network and pushes local flow excess toward the sink along what are estimated to be shortest paths. The algorithm and its analysis are simple and intuitive, yet the algorithm runs as fast as any other known method on dense.graphs, achieving an O(n)) time bound on an n-vertex graph. By incorporating the dynamic tree data structure of Sleator and Tarjan, we obtain a version of the algorithm running in O(nm log(n’/m)) time on an n-vertex, m-edge graph. This is as fast as any known method 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 n processors and O(m) space is obtained. This time bound matches that of the Shiloach-Vishkin algorithm, which also usesn processorsbut requires O(n’) space.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Non- numerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph Theory-graph algorithms; network problems
75

Maximum-flow algorithms: practice
Caveat. Worst-case running time is generally not useful for predicting or comparing max-flow algorithm performance in practice.
Best in practice. Push–relabel method with gap relabeling: O(m3/2) in practice.
On Implementing Push-Relabel Method for the Maximum Flow Problem
Boris V. Cherkassky 1 and Andrew V. Goldberg2
1 Central Institute for Economics and Mathematics, Krasikova St. 32, 117418, Moscow, Russia cher@eemi.msk.su
2 Computer Science Department, Stanford University Stanford, CA 94305, USA
goldberg~cs. stanford,edu
EUROPEAN JOURNAL
OF OPERATIONAL RESEARCH
Abstract.
for the maximum flow problem. The resulting codes are faster than the previous codes, and much faster on some problem families. The speedup is due to the combination of heuristics used in our implementations. We also exhibit a family of problems for which the running time of all known methods seem to have a roughly quadratic growth rate.
1 Introduction
The rnaximum flow problem is a classical combinatorial problem that comes up in a wide variety of applications. In this paper we study implementations of the push-rdabel [13, 17] method for the problem.
The basic methods for the maximum flow problem include the network sim- plex method of Dantzig [6, 7], the augmenting path method of Ford and F~lker-
Ravindra K. Ahuja a, Murali Kodialam b, Ajay K. Mishra c, James B. Orlin d,.
a Department t~’lndustrial and Management Engineering. Indian Institute of Technology. Kanpur, 208 016, India bAT& T Bell Laboratories, Holmdel, NJ 07733, USA
c KA’F-ZGraduate School of Business, University of Pittsburgh, Pittsburgh, PA 15260, USA
d Sloun School of Management, Massachusetts Institute of Technology. Cambridge. MA 02139. USA
Received 30 August 1995; accepted 27 June 1996
We study efficientimplementations ofthe push-relabel method
E L S E V I E R
European Journal of Operational Research 97 (1997) 509-542
Theory and Methodology
Abstract
Computational investigations of maximum flow algorithms
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
have produced improvements in practice. The purpose of this paper is to test some of the major algorithmic ideas developed
in the recent years and to assess their utility on the empirical front. However, our study differs from previous studies in 76 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
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

Maximum-flow algorithms: practice
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 Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision
Yuri Boykov and Vladimir Kolmogorov∗ Abstract
After [15, 31, 19, 8, 25, 5] minimum cut/maximum flow algorithms on graphs emerged as an increasingly useful tool for exact or approximate energy minimization in low-level vision. The combinatorial optimization literature provides many min-cut/max-flow algorithms with 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 new algorithm that we have recently developed. The algorithms we study include both Goldberg-Tarjan style “push-relabel” methods and algorithms based on Ford-Fulkerson style “augmenting paths”. We benchmark these algorithms on a number of typical graphs in the contexts of image restoration, stereo, and segmentation. In many cases our new algorithm works several times faster than any of the other methods making near real-time performance possible. An implementation of our max-flow/min-cut algorithm is available upon request for research purposes.
Index Terms — Energy minimization, graph algorithms, minimum cut, maximum
VERMA, BATRA: MAXFLOW REVISITED 1
MaxFlow Revisited:
An Empirical Comparison of Maxflow Algorithms for Dense Vision Problems
Tanmay Verma
tanmay08054@iiitd.ac.in
Dhruv Batra
dbatra@ttic.edu
IIIT-Delhi Delhi, India
TTI-Chicago Chicago, USA
Abstract
Algorithms for finding the maximum amount of flow possible in a network (or max- 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 from energy minimization problems in Object Category Segmentation, Image Deconvo- lution, Super Resolution, Texture Restoration, Character Completion and 3D Segmen- 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 for dense graphs.
flow, image restoration, segmentation, stereo, multi-camera scene reconstruction.
∗Yuri Boykov is with the Computer Science Department at the University of Western Ontario, Canada, yuri@csd.uwo.ca. Vladimir Kolmogorov is with Microsoft Research, Cambridge, England, vnk@microsoft.com. This work was mainly done while the authors were with Siemens Corp. Research, Princeton, NJ.
1 Introduction
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- chine learning – from optimal (or provably-approximate) inference in sophisticated discrete
77

Maximum-flow algorithms: Matlab
78

Maximum-flow algorithms: Google
79

Network flow: quiz 7
Which max-flow algorithm to use for bipartite matching? 
A. Ford–Fulkerson: O(m n C).
B. Capacity scaling: O(m2 log C).
C. Shortest augmenting path: O(m2 n).
D. Dinitz’ algorithm: O(m n2).
we’ll show that Dinitz’ algorithm runs in O(m n1/2) time for bipartite matching
SIAM J. CoMavx.
Vol. 4, No. 4, December 1975
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 thenshownthatifthevertexcapacitiesareallequaltoone,thealgorithmrequiresatmostO(IV[1/2 IEI) time, and if the edge capacities are all equal to one, the algorithm requires at most O(I VI2/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(IVI1/z. IEI2) time and the edge connectivity in O(IV[5/3. IEI) time.
Key words. Dinic’s algorithm, maximum flow, connectivity, vertex connectivity, edge connec- tivity
1. Network flow. Let G(V, E) be a finite directed graph, where V is the set of
81

Simple unit-capacity networks
D・ef. A flow network is a simple unit-capacity network if: ・Every edge has capacity 1.
Every node (other than s or t) has exactly one entering edge, or exactly one leaving edge, or both.
node capacity = 1
Property. Let G be a simple unit-capacity network and let f be a 0–1 flow. Then, residual network Gf is also a simple unit-capacity network.
Ex. Bipartite matching. 1
1
1
82

Simple unit-capacity networks
Shortest-augmenting-path algorithm.
・Normal augmentation: length of shortest path does not change. ・Special augmentation: length of shortest path strictly increases.
Theorem. [Even–Tarjan 1975] In simple unit-capacity networks, Dinitz’ algorithm computes a maximum flow in O(m n1/2) time. P・f.
・Lemma 1. Each phase of normal augmentations takes O(m) time. ・Lemma 2. After n1/2 phases, val( f ) ≥ val( f *) – n1/2.
Lemma 3. After ≤ n1/2 additional augmentations, flow is optimal. ▪ Lemma 3. After ≤ n1/2 additional augmentations, flow is optimal.
Pf. Each augmentation increases flow value by at least 1. ▪ Lemma 1 and Lemma 2. Ahead.
83

Simple unit-capacity networks
within a phase, length of shortest augmenting path does not change
・Start at s, advance along an edge in LG until reach t or get stuck. ・If reach t, augment flow; update L ; and restart from s.
If get stuck, delete node from L and go to previous node. G
construct level graph
P・hase of normal augmentations. ・Construct level graph L .
G
G
st
level graph LG
84

Simple unit-capacity networks
Phase of normal augmentations.
・Construct level graph LG.
・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 get stuck, delete node from LG and go to previous node.
advance
st
level graph LG
85

Simple unit-capacity networks
Phase of normal augmentations.
・Construct level graph LG.
・Start at s, advance along an edge in LG until reach t or get stuck.
・If reach t, augment flow; update L ; and restart from s. G
If get stuck, delete node from L and go to previous node. G
augment
remove from level graph all edges in augmenting path
st
level graph LG
86

Simple unit-capacity networks: analysis
Phase of normal augmentations.
・Construct level graph LG.
・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 get stuck, delete node from LG and go to previous node.
Lemma 1. A phase of normal augmentations takes O(m) time. Pf.
・O(m) to create level graph LG.
O(1) per edge (each edge involved in at most one advance, retreat, and
・augmentation).
O(1) per node (each node deleted at most once). ▪
92

Network flow: quiz 8
Consider running advance–retreat algorithm in a unit-capacity network (but not necessarily a simple one). What is running time? 
both indegree and outdegree of a node can be larger than 1
A. O(m).
B. O(m3/2).
C. O(m n).
D. May not terminate.
useful for this week’s homework!
93

Simple unit-capacity networks: analysis
L・emma 2. After n1/2 phases, val( f ) ≥ val( f *) – n1/2.
・After n1/2 phases, length of shortest augmenting path is > n1/2.
・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 ⇒ ⎢V ⎢ ≤ n1/2. h
・Let A = {v : l(v) < h} ∪ {v : l(v) = h and v has ≤ 1 outgoing residual edge}. cap(A,B)≤⎢V⎢≤n1/2 ⇒val(f)≥val(f*)–n1/2.▪ residual network Gf A unit-capacity simple network fh residual edges st V1 Vh Vn1/2 95 Simple unit-capacity networks: review Theorem. [Even–Tarjan 1975] In simple unit-capacity networks, Dinitz’ algorithm computes a maximum flow in O(m n1/2) time. P・f. ・Lemma 1. Each phase takes O(m) time. ・Lemma 2. After n1/2 phases, val( f ) ≥ val( f *) – n1/2. Lemma 3. After ≤ n1/2 additional augmentations, flow is optimal. ▪ Corollary. Dinitz’ algorithm computes max-cardinality bipartite matching in O(m n1/2) time. 96

Related Posts