[SOLVED] CS data mining ER algorithm The University of Sydney

The University of Sydney
Page 1
From Jeff Ericksons http://algorithms.wtf

Lecture 5
Dynamic Programming II (continued)
The University of Sydney
Page 2

6.8 Shortest Paths
The University of Sydney Page 3

Shortest Paths
Shortest path problem. Given a directed graph G = (V, E), with edge weights cvw, find shortest path from node s to node t.
allow negative weights
2 10 3
9
s
18
30
5
-8
20
7
6
6
15
-16 6
4 19
6 16
t
11
44
The University of Sydney
Page 4

Shortest Paths: Failed Attempts
Dijkstra. Can fail if negative edge costs.
u
3
sv
-6 t
Re-weighting. Adding a constant to every edge weight can fail. 55
The University of Sydney
Page 5
2
1
22
s6 6t
3
-3
3
Paths with more edges are penalized more
0

Shortest Paths: Negative Cost Cycles
Negative cost cycle.
-6
-4 7
Observation. If some path from s to t contains a negative cost cycle, there does not exist a shortest s-t path; otherwise, there exists one that is simple and thus has at most n 1 edges.
st
W c(W) < 0 The University of SydneyPage 6 Shortest Paths: Dynamic ProgrammingProblem: Find shortest path from s to t Step 1: Define subproblemsOPT(i, v) = length of shortest v-t path P using at most i edges.The University of SydneyPage 7svt i edges Shortest Paths: Dynamic Programming Step 2: Find recurrencesvt The University of SydneyPage 8Case 1: P uses at most i-1 edges. OPT(i, v) = OPT(i-1, v) i-1 edges Shortest Paths: Dynamic ProgrammingStep 2: Find recurrencesCase 1: P uses at most i-1 edges. OPT(i, v) = OPT(i-1, v) Case 2: P uses exactly i edges.t if (v, w) is first edge, then OPT uses (v, w), and then selects best w-t path using at most i-1 edgeswtv i-1 edgesv i-1 edgesOPT(i,v) =min{OPT(i-1,v), min [OPT(i-1,w)+cvw] } (v,w)IEThe University of SydneyPage 9 Shortest Paths: Dynamic Programming Step 3: Solve the base casesOPT(0,t) = 0 and OPT(0,v=t) = The University of SydneyPage 10 Shortest Paths: Dynamic ProgrammingStep 1: OPT(i, v) = length of shortest v-t path P using at most i edges.Step 2:Case 1: P uses at most i-1 edges. OPT(i, v) = OPT(i-1, v)Case 2: P uses exactly i edges. if (v, w) is first edge, then OPT uses (v, w), and then selectsbest w-t path using at most i-1 edgesStep 3: OPT(0,t) = 0 and OPT(0,v=t) = 0 if i=0 and v=t OPT(i,v) = if i=0 and v=tmin{OPT(i-1,v), min [OPT(i-1,w)+cvw] } otherwiseThe University of Sydney(v,w)IEPage 11 Shortest Paths: ImplementationShortest-Path(G, t) { foreach node v I VM[0, v] M[0, t] 0for i = 1 to n-1foreach node v I V O(m)O(n) iterations}M[i, v] M[i-1, v] foreach edge (v, w) I EM[i,v] min{M[i,v],M[i-1,w]+cvw}iterations Analysis. Q(mn) time, Q(n2) working space.Space used by algorithm in addition to input Finding the shortest paths. Maintain a “successor” for each table entry. Successor(i,v) = next vertex on shortest v-t path with at most i edges.The University of Sydney Page 12 Shortest Paths: Efficient Implementation Shortest-Path(G, t) { foreach node v I VM[0, v] M[0, t] 0for i = 1 to n-1 foreach node v I V}M[i, v] M[i-1, v] foreach edge (v, w) I EM[i,v] min{M[i,v],M[i-1,w]+cvw} only need Analysis. Q(mn) time, Q(n) working space. M[i-1, *]values Finding the shortest paths. Maintain a “successor” for vertex. In the i-th iteration, Successor(v) = next vertex on shortest v-t path with at most i edges.The University of Sydney Page 13In iteration i, Bellman-Ford: Efficient Implementation Push-Based-Shortest-Path(G, s, t) { foreach node v I V {M[v] successor[v] } M[t] = 0 for i = 1 to n-1 {foreach node w I V {if (M[w] has been updated in previous iteration) {foreach node v such that (v, w) I E { if (M[v] > M[w] + cvw) {
M[v] M[w] + cvw
successor[v] w }
} }
If no M[w] value changed in iteration i, stop.
}
}
Analysis: Q(mn) time, Q(n) working space. The University of Sydney Page 14

Shortest Paths: Practical Improvements
Practical improvements
Maintain only one array M[v] = shortest v-t path that we have
found so far.
No need to check edges of the form (v, w) unless M[w] changed in previous iteration.
Theorem: Throughout the algorithm, M[v] is length of some v-t path, and after i rounds of updates, the value M[v] is no larger than the length of shortest v-t path using i edges.
Overall impact
Working space: O(n).
Total space (including input): O(m+n)
Running time: O(mn) worst case, but substantially faster in practice.
The University of Sydney
Page 15
15

Dynamic Programming Summary I
3 steps:
1. Definesubproblems
2. Findrecurrences
3. Solvethebasecases
4. Transformrecurrenceintoanefficientalgorithm [usually bottom-up]
The University of Sydney
Page 16
16

Dynamic Programming Summary II
1D dynamic programming
Weighted interval scheduling
Segmented Least Squares
Maximum-sum contiguous subarray Longest increasing subsequence
2D dynamic programming Knapsack
Shortest path
Longest common subsequence
Dynamic programming over intervals RNA Secondary Structure
The University of Sydney
Page 17

General techniques in this course
Greedy algorithms [Lecture 2]
Divide & Conquer algorithms [Lecture 3]
Dynamic programming algorithms [Lectures 4 and 5] Network flow algorithms [today and Lecture 7-8]
Theory [today]
Applications [Lectures 7-8]
NP and NP-completeness Coping with hardness
The University of Sydney
Page 18

Soviet Rail Network, 1955
The University of Sydney
Page 20
Reference: On the history of the transportation and maximum flow problems. Alexander Schrijver in Math Programming, 91: 3, 2002.

Maximum Flow and Minimum Cut
Max flow and min cut.
Two very rich algorithmic problems.
Cornerstone problems in combinatorial optimization.
Mathematical duality.
Nontrivial applications / reductions.
Data mining.
Open-pit mining.
Project selection.
Airline scheduling.
Bipartite matching.
Baseball elimination.
Image segmentation.
Network connectivity.
Network reliability.
Distributed computing.
Egalitarian stable matching.
Securityofstatisticaldata.
Network intrusion detection.
Multi-camera scene reconstruction.
Manymanymore
The University of Sydney
Page 21

Flow network
Abstraction for material flowing through the edges.
G = (V, E): a directed graph with no parallel edges.
Two distinguished nodes: s = source, t = sink.
The source has no incoming edges and the sink has no outgoing edges.
c(e) = capacity of edge e. 295
10
sources 5 3 8 6
4
15 15
10
10 tsink 10
Page 22
capacity
The University of Sydney
15
46
15 4 30 7

Flows
Definition: An s-t flow is a function that satisfies: For each e I E: 0 f(e) c(e)
We say e is saturated if f(e) = c(e)
For each v I V {s, t}: a f(e) =
(capacity) (conservation)
e in to v
Definition: The value of a flow f is:
a f(e) e out of v
The University of Sydney
0
Value =Pa4ge 23
capacity 10 flow 4
0
15 15 0
v( f ) = 2 9 5
a f (e) . e out of s
0
10
4
0
10
44
s 5 3 8 6 10 t
0
04
15
0
40 6 150 0
4 30 7

Flows
Definition: An s-t flow is a function that satisfies: For each e I E: 0 f(e) c(e)
We say e is saturated if f(e) = c(e)
For each v I V {s, t}: a f(e) =
(capacity) (conservation)
e in to v
Definition: The value of a flow f is:
a f(e) e out of v
v( f ) = 2 9 5
a f (e) . e out of s
6
10
8
6
capacity 10
15 15 0 0
44
s 5 3 8 6 10 t
flow 10 38
15
11
40 6 150 1
4 30 7
10
10
The University of Sydney
11
Value =P2ag4e 24

Maximum Flow Problem
Max flow problem. Find s-t flow of maximum value.
Question: How to characterize optimal solution?
DP and D&C uses a recurrence equation. Not known if max flows admit such a recurrence.
2 9 5
9
capacity 10
15 15 0 1
9
10
9
40
s 5 3 8 6 10 t
flow 10 48
15
14
40 6 150 4
4 30 7
10
10
The University of Sydney
14
Value =P2ag8e 25

Characterizing Max Flow
Simple conditions implying f is a max flow: f saturates every edge out of s OR
f saturates every edge out of t
2 9 5
9
capacity 10
15 15 0 1
9
10
9
40
s 5 3 8 6 10 t
flow 10 48
15
14
40 6 150 4
4 30 7
10
10
The University of Sydney
14
Value =P2ag8e 26

Cuts
Definitions:
Ans-tcutisapartition(A,B)ofVwithsIAandtIB.
cap(A,B) = Only count capacity of outgoing edges!
a c(e) e out of A
The capacity of a cut (A, B) is: 295
10
4
15 15
10
s 5 3 8 6 10 t A
15
46
10
15 4 30 7
Capacity = 10 + 5 + 15
The University of Sydney
= 30
Page 27

Cuts
Definitions:
Ans-tcutisapartition(A,B)ofVwithsIAandtIB.
a c(e) e out of A
cap(A,B) = Only count capacity of outgoing edges!
The capacity of a cut (A, B) is:
2 9 5
10
15 15
s 5 3 8 6 10 t
4
10
A
The University of Sydney
15 4 30 7
15
46
10
Capacity = 9 + 15 + 8 + 30
= 62
Page 28

Minimum Cut Problem
Min s-t cut problem:
Find an s-t cut of minimum capacity.
Question: How to characterize optimal solution?
Not known if min cuts admit a DP-style recurrence.
2 9 5
10
4
15
s 5 3 8 6 10 t
15
10
A
The University of Sydney
15
46
4 30 7
10
15
Capacity = 10 + 8 + 10
= 28
Page 29

Max-Flow = Min-Cut
1. Max-Flow Min-Cut
2. AlgorithmforMax-Flowfindsaflowfandacut(A,B)such that v(f) = cap(A,B)
2 9 5
9
capacity 10
15 15 0 1
9
10
9
40
s 5 3 8 6 10 t
flow 10 48
15
14
40 6 150 4
4 30 7
10
10
The University of Sydney
14
Value =P2ag8e 30

Notation
Given a vertex u, define fout(u) = total flow on edges leaving u
Given a vertex subset S, define fout(S) = total flow on edges leaving S
Similarly, define fin(u) and fin(S) on edges entering u and S, resp.
Can rewrite v(f) = fout(s) and fin(u) = fout(u) for v not s,t
6
2 9 5
10
10
44
0
15 15 0
6
10
388
s 5 3 8 6 10 t
The University of Sydney
4 30 7
A
1
40 6 150
11
10
10
15
11
Value = 10+3+11 = 24Page 31

Flows and Cuts
Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount
leaving s.
v(f) = fout(A) fin(A)
6
2 9 5
10
10
44
0
15 15 0
6
10
388
s 5 3 8 6 10 t
A
1
40 6 150
11
10
10
15
11
Value = 10+3+11 = 24Page 34
The University of Sydney
4 30 7

Flows and Cuts
Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount
leaving s.
v(f) = fout(A) fin(A) 6
The University of Sydney
7
Value = 6 + 0 + 8 1 + 11 = 24 Page 35
A
1
40 6 150
10
10
10
10
44
0
15 15 0
6
10
2 9 5
388
s 5 3 8 6 10 t
15
11
11
4 30

Flows and Cuts
Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount
leaving s.
v(f) = fout(A) fin(A) 6
2 9 5
10
10
44
0
15 15 0
6
10
388
s 5 3 8 6 10 t
A
1
40 6 150
10
10
15
11
11
4 30
The University of Sydney
7
Value = 10 4 + 8 0 + 10 = 24 Page 36

Proof of flow value lemma
Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount
leaving s.
Proof:
v(f) = fout(A) fin(A)
v(f) = fout(s) = fout(s) fin(s)
The University of Sydney
Page 37
by flow conservation, all terms except v = s are 0, i.e. fout(v) fin(v) = 0
= S (fout(v) fin(v)) vIA
=S f(e)Sf(e)
e out of A
e into A = fout(A) fin(A)

Flows and Cuts
Weak duality. Let f be any flow, and let (A, B) be any s-t cut. Then the value of the flow is at most the capacity of the cut, i.e.
v(f) cap(A, B)
Cut capacity = 30 Flow value 30 2 9 5
10
4
15 15
10
s 5 3 8 6 10 t A
15
46
10
15 4 30 7
The University of Sydney
Capacity = P3ag0e 39

Flows and Cuts
Weak duality. Let f be any flow, and let (A, B) be any s-t cut. Then the value of the flow is at most the capacity of the cut, i.e.
v(f) cap(A, B)
Cut capacity = 28 Flow value 28 2 9 5
10
4
15 15
10
s 5 3 8 6 10 t A
15 4 30 7
15
46
10
The University of Sydney
Capacity = P2ag8e 40

Flows and Cuts
Weak duality. Let f be any flow, and let (A, B) be any s-t cut. Then the value of the flow is at most the capacity of the cut, i.e.,
Proof:
v(f) = =
=
fout(A) fin(A)
fout(A)
S f(e) e out
of A
Sc(e) e out
of A c(A,B)
A
8
B
t
The University of Sydney
Page 41
v(f) cap(A, B).
s
7
6
4

Certificate of Optimality
Corollary: Let f be any flow, and let (A, B) be any cut.
If v(f) = cap(A, B) then f is a max flow and (A, B) is a min cut.
Value of flow = 28
Cut capacity = 28 Flow value 28
9
2 9 5
10
10
1
15 15 0
9
10
40 489
s 5 3 8 6 10 t
4
A 15 40 6 150
10
10
The University of Sydney
4 30 7
Page 42
14
14

Summary (so far)
The University of Sydney
Page 43
1. Max flow problem
2. Min cut problem
3. Theorem: Max flow Min cut

Towards a Max Flow Algorithm
Greedy algorithm.
Startwithf(e)=0foralledgeeIE.
Find an s-t path P where each edge has f(e) < c(e). Augment flow as much flow as possible along path P. Repeat until you get stuck. 10020 10s 300 t10 2000Flow value = 0 The University of SydneyPage 442 Towards a Max Flow AlgorithmGreedy algorithm. Startwithf(e)=0foralledgeeIE. Find an s-t path P where each edge has f(e) < c(e). Augment as much flow as possible along path P. Repeat until you get stuck. 1s s3 0 X0 2 0t t20 X02001010020X0 2 0Flow value = 20 The University of SydneyPage 452 Towards a Max Flow AlgorithmAugmenting greedy flow to get optimal flow1120 0 20 1020 10 20 10s 3020 t s 3010 t10 20 10 200 20 10 2022TgherUeniverdsityof=Syd2ne0y opt = 30 Page 46 Towards a Max Flow AlgorithmAugmenting greedy flow to get optimal flow Send 10 units on (s,2) edge1120 0 20 1020 10 20 10s 3020 t s 3010 t10 20 10 2010 20 10 2022TgherUeniverdsityof=Syd2ne0y opt = 30 Page 47Towards a Max Flow AlgorithmAugmenting greedy flow to get optimal flow Send 10 units on (s,2) edge Undo 10 units on (1,2) edge to preserve conservation at vertex 21120 0 20 1020 10 20 10s 3010 t s 3010 t10 20 10 2010 20 10 2022TgherUeniverdsityof=Syd2ne0y opt = 30 Page 48 Towards a Max Flow AlgorithmAugmenting greedy flow to get optimal flow Send 10 units on (s,2) edge Undo 10 units on (1,2) edge to preserve conservation at vertex 2 Send 10 units on (1,t) edge to preserve conservation at vertex 11120 10 20 1020 10 20 10s 3010 t s 3010 t10 20 10 2010 20 10 2022TgherUeniverdsityof=Syd2ne0y opt = 30 Page 49 Build a Residual Graph Gf = (V, Ef ) Original edge: e = (u, v) I E. Flowf(e),capacityc(e). Residualedge. e=(u,v)andeR =(v,u).capacityu 17 v6flowresidual capacity u 11 v IfeinE,theneisaforwardedge,elsebackwardedge Residualcapacity:cf(e)=iic(e)-f(e) ifeIE if(e) if eR IE Residual graph: Gf = (V, Ef ). Residualedgeswithpositiveresidualcapacity.6 Residualcapacityofforwardedgeerepresentssparecapacityofe ResidualcapacityofbackwardedgeeRrepresentscurrentflowonethat Ef ={e:f(e) 0}.
MaxflowofGf=(MaxflowofG)v(f)(Exercise)
The University of Sydney Page 50
residualcapacity

Augmenting Path Algorithm
Notations:
P = a simple s-t path in Gf
bottleneck(P,f) = minimum residual capacity of any edge on P with respect to the current flow f.
u 20
G
s
10
10 30
t 20
v
u 10 Gf 20
s 30 10
v
t 20
The University of Sydney
Page 52

Augmenting Path Algorithm
Notations:
P = a simple s-t path in Gf
bottleneck(P,f) = minimum residual capacity of any edge on P with respect to the current flow f.
0/10
s
v
u 20/30
G
20/20 s
0/10
t 20/20
v
u Gf
t
The University of Sydney
Page 53

Augmenting Path Algorithm
Notations:
P = a simple s-t path in Gf
bottleneck(P,f) = minimum residual capacity of any edge on P with respect to the current flow f.
u 20/30
G
t 20/20
u Gf 10
20/20 s
0/10
v
0/10
20
s 10
v
20 10
t 20
The University of Sydney
Page 54

Augmenting Path Algorithm
Notations:
P = a simple s-t path in Gf
bottleneck(P,f) = minimum residual capacity of any edge on P with respect to the current flow f.
u 20/30
G
t 20/20
u Gf 10
Augment(f,P) {
b bottleneck(P,f) foreach e =(u,v) I P {
if e is a forward edge then
increase f(e) in G by b
else (e is a backward edge)
decrease f(e) in G by b
}
return f }
20/20 s
0/10
v
0/10
20
s 10
v bottleneck
20 10
t 20
The University of Sydney
Page 55

Augmenting Path Algorithm
Notations:
P = a simple s-t path in Gf
bottleneck(P,f) = minimum residual capacity of any edge on P with respect to the current flow f.
The University of Sydney
u s 10/30
G
Augment(f,P) {
b bottleneck(P,f) foreach e =(u,v) I P {
if e is a forward edge then
increase f(e) in G by b
else (e is a backward edge)
decrease f(e) in G by b
}
return f }
20/20
t
10/10
10/10
v
u Gf 10
20/20
20
s 10
v
Augment(f,P) gives a new flow f in G with v(f) = b + v(f) Page 56
20 10
t 20

Augmenting Path Algorithm
Ford-Fulkerson(G,s,t) { foreach e I E
f(e) 0
Gf residual graph
while (there exists augmenting path P in Gf){ f Augment(f,P)
update Gf }
return f }
Augment(f,P) {
b bottleneck(P,f) foreach e =(u,v) I P {
if e is a forward edge then
increase f(e) in G by b
else (e is a backward edge)
decrease f(e) in G by b
}
return f }
Page 57
The University of Sydney

Ford-Fulkerson Algorithm
244
10 2 8 6 10
s 10 3 9 5 10 t
G:
capacity
The University of Sydney Page 58

Ford-Fulkerson Algorithm
0
2 4 4
flow
capacity
G:
s 10 3 9 5 10 t
0 10208 6010
00 000
The University of Sydney
Page 59
Flow value = 0

Ford-Fulkerson Algorithm
0
2 4 4
flow
capacity
G:
s 10 3 9 5 10 t
0 10208 6010
8X0 0 X8
0 0 8X0
Flow value = 0
244
residual capacity 10
Gf:
10
2
86
s 10 3 9 5 10 t
The University of Sydney
Page 60

Ford-Fulkerson Algorithm
G:
0
2 4 4
1 0 X8 8
10208 6010
s 10 3 X 5 t 9 10
X
0 2 02 10X8
0
2 4 4
Flow value = 8
Gf:
8
2
86
10
2 s 10 3
9 5 2 t 8
The University of Sydney
Page 61

Ford-Fulkerson Algorithm
G:
0
2 4 4
X0 6 1022 X10
X06
s 10 3 X 5
2 4 4
10 2 8 6 10
10 8
860
28
9 10
t
Flow value = 10
6 10
Gf:
s 10 3 7 5 10 t 2
The University of Sydney
Page 62

Ford-Fulkerson Algorithm
2 4 4
02 X
G:
s 10 3 9 5 10 t
X6 8 10 22 8 66 10
10 8 X0
X68 8 10
Flow value = 16
Gf:
2 4 4
10 2 8 6 4
6
s 4 3 1 5 10 t
The University of Sydney
Page 63
6
8

Ford-Fulkerson Algorithm
G:
23 X
2 4 4
X8 9 10 20 8 66 10
10 87 X
X8 9 8 9 1 0 s 10 3 X 5
t
Flow value = 18
8
9 10
Gf:
2
2 2 4
10 2 8 6 2
s 2 3 1 5 10 t
The University of Sydney
Page 64
8
8

Ford-Fulkerson Algorithm
3
2 4 4
G:
s 10 3 9 5 10 t
9 10 20 8 66 10
10 7
9 9 10
3
2 1 4
Gf: 1 9
Flow value = 19
10 2 7
6 1
s 1 3 9 5 10 t 9
The University of Sydney
Page 65

Ford-Fulkerson Algorithm
G:
3
2 4 4
9 10 20 8 66 10
10 7
9 9 10
s 10 3 9 5 10 t
Cut capacity = 19 Flow value = 19
3
2 1 4
Gf: 1 9
The University of Sydney
Page 66
10 2 7
s 1 3 9 9
6 1
5 10 t

Augmenting Path Algorithm
Ford-Fulkerson(G,s,t) { foreach e I E
f(e) 0
Gf residual graph
while (there exists augmenting path P in Gf){ f Augment(f,P)
update Gf }
return f }
Augment(f,P) {
b bottleneck(P,f) foreach e =(u,v) I P {
if e is a forward edge then
increase f(e) in G by b
else (e is a backward edge)
decrease f(e) in G by b
}
return f }
Page 67
The University of Sydney

Max-Flow Min-Cut Theorem
Augmenting path theorem: Flow f is a max flow if and only if there are no augmenting paths.
Max-flow min-cut theorem: The value of the max flow is equal to the value of the min cut. [Ford-Fulkerson 1956]
Proof strategy: We prove both simultaneously. Let f be a flow. Then the following are equivalent:
(i) There exists a cut (A, B) such that v(f) = cap(A, B). (ii) Flow f is a max flow.
(iii) There is no augmenting path relative to f.
(i) (ii) This was the corollary to the weak duality lemma.
(ii) (iii) We show contrapositive.
Letfbeaflow.Ifthereexistsanaugmentingpath,thenwecanimprovef
by sending flow along a path P and augment the flow in G.
The University of Sydney Page 68

Proof of Max-Flow Min-Cut Theorem
(iii) (i)
Let f be a flow with no augmenting paths.
Let A be set of vertices reachable from s in residual graph. BydefinitionofA,sIA.
Bydefinitionoff,tIA.
v(f)= X f(e) X f(e) e out of A e into A
A
B
t
s
The University of Sydney
original network
Page 69

Proof of Max-Flow Min-Cut Theorem
(iii) (i)
Let f be a flow with no augmenting paths.
Let A be set of vertices reachable from s in residual graph. BydefinitionofA,sIA.
Bydefinitionoff,tIA.
v(f)= X f(e) X f(e) e out of A e into A
A
B
t
No augmenting path from A to B => every edge leaving A saturated, every edge entering A is empty
s
The University of Sydney
original network
Page 70

Proof of Max-Flow Min-Cut Theorem
(iii) (i)
Let f be a flow with no augmenting paths.
Let A be set of vertices reachable from s in residual graph. BydefinitionofA,sIA.
Bydefinitionoff,tIA.
v(f)= X f(e) X f(e) e out of A e into A
= c(e) e out of a
= cap(A, B)
No augmenting path from A to B => every edge leaving A saturated, every edge entering A is empty
A
B
t
s
The University of Sydney
original network
Page 71

Max-Flow Min-Cut Theorem
Augmenting path theorem: Flow f is a max flow if and only if there are no augmenting paths.
Max-flow min-cut theorem: The value of the max flow is equal to the value of the min cut. [Ford-Fulkerson 1956]
Proof strategy: We prove both simultaneously. Let f be a flow. Then the following are equivalent:
(i) There exists a cut (A, B) such that v(f) = cap(A, B). (ii) Flow f is a max flow.
(iii) There is no augmenting path relative to f.
Note: This implies we can check if a given flow f is max flow in time O(n + m)!
The University of Sydney Page 72

Ford-Fulkerson: Analysis
Assumption. All initial capacities are integers.
Lemma. At every intermediate stage of the Ford-Fulkerson algorithm
the flow values and the residual graph capacities in Gf are integers.
Proof: (proof by induction)
Base case: Initially the statement is correct. Induction hyp.: True after j iterations.
Induction step: Since all the residual capacities in Gf are integers the bottleneck-value must be an integer. Thus the flow will have integer values and hence also the capacities in the new residual graph.
Integrality theorem. If all capacities are integers, then there exists a max flow f for which every flow value f(e) is an integer.
The University of Sydney Page 73

Ford-Fulkerson: Running Time
Observation:
Let f be a flow in G, and let P be a simple s-t path in Gf. v(f) = v(f) + bottleneck(f,P)
and since bottleneck(f,P)>0 v(f) > v(f).
The flow value strictly increases in an augmentation
Theorem. The algorithm terminates in at most v(fmax) F iterations, where F = value of max flow.
Proof: Each augmentation increase flow value by at least 1.
The University of Sydney Page 74

Ford-Fulkerson: Running Time
Corollary:
Ford-Fulkerson runs in O((m+n)F) time, if all capacities are integers.
Proof: C iterations.
Path in Gf can be found in O(m+n) time using BFS. Augment(P,f) takes O(n) time.
Updating Gf takes O(n) time.
The University of Sydney
Page 75

7.3 Choosing Good Augmenting Paths
Is O(F(m+n)) a good time bound?
Yes, if F is small.
If F is large, can the number of iterations be as bad as F?
The University of Sydney Page 76

Ford-Fulkerson: Exponential Number of Augmentations
Question: Is generic Ford-Fulkerson algorithm polynomial in
input size?
Answer: No. If max capacity is D, then algorithm can take D iterations.
1
1X0 0
DD
s 1X01 t
m, n, and log C
D
D
00 X1
2
The University of Sydney
Page 77

Ford-Fulkerson: Exponential Number of Augmentations
Question: Is generic Ford-Fulkerson algorithm polynomial in
input size?
Answer: No. If max capacity is D, then algorithm can take D iterations.
11
1 X0 0 1 X0 X0 1 DDDD
s 1X01 t s 1X0X10 t DDDD
0 0 10 X01 X1X
m, n, and log C
22
The University of Sydney
Page 78

Choosing Good Augmenting Paths
Use care when selecting augmenting paths.
Some choices lead to exponential algorithms.
Clever choices lead to polynomial algorithms.
If capacities are irrational, algorithm not guaranteed to terminate!
Goal: choose augmenting paths so that: Can find augmenting paths efficiently.
Few iterations.
Choose augmenting paths with: [Edmonds-Karp 1972, Dinitz 1970] Max bottleneck capacity.
Sufficiently large bottleneck capacity.
Fewest number of edges.
The University of Sydney Page 79

Choosing Good Augmenting Paths
Ford Fulkerson
Choose any augmenting path (C iterations)
Edmonds Karp #1 (m log C iterations) Choose max flow path
Improved Ford Fulkerson via capacity scaling (log C iterations) Choose max flow path
Edmonds Karp #2 (O(nm) iterations)
Choose minimum link path [Edmonds-Karp 1972, Dinitz 1970]
The University of Sydney Page 80

Edmonds-Karp #1
Pick the augmenting path with largest capacity [maximum bottleneck path]
The University of Sydney Page 81

Edmonds-Karp #1
Pick the augmenting path with largest capacity [maximum bottleneck path]
Claim: If maximum flow in G is F, there must exists a path from s to t with bottleneck capacity at least F/m.
The University of Sydney Page 82

Edmonds-Karp #1
Pick the augmenting path with largest capacity [maximum bottleneck path]
Claim: If maximum flow in G is F, there must exists a path from s to t with bottleneck capacity at least F/m.
Proof:
Delete all edges of capacity less than F/m.
Is the graph still connected?
F=24 m=15
6 10 t
2 9
15 s 5 3 8
5
15 10
10
4
15
4 6 15 4 30 7
10
The University of Sydney
Page 83

Edmonds-Karp #1
Pick the augmenting path with largest capacity [maximum bottleneck path]
Claim: If maximum flow in G is F, there must exists a path from s to t with bottleneck capacity at least F/m.
Proof:
Delete all edges of capacity less than F/m.
Is the graph still connected?
Yes, otherwise we have a cut of value less than F.
A
B
t
< F/m s The University of Sydney< F/mPage 84 Edmonds-Karp #1Pick the augmenting path with largest capacity [maximum bottleneck path]Claim: If maximum flow in residual graph Gf is F, there must exists a path from s to t with bottleneck capacity at least F/m.Proof:Delete all edges of capacity less than F/m.Is the graph still connected?Yes, otherwise we have a cut of value less than F.ABt< F/m s The University of Sydney< F/mPage 85 Edmonds-Karp #1Theorem: Edmonds-Karp #1 makes at most O(m log F) iterations.Proof:At least 1/m of remaining flow is added in each iteration.URemaining flow reduced by a factor of (1-1/m) per iteration. #iterations until remaining flow <1? F(1-1/m)x <1?We know: (1-1/m)m < 1/eSet x = m ln F F (1-1/m)m ln F < F (1/e)ln F = 1 The University of SydneyPage 88 ApplicationsThe University of SydneyPage 89 Bipartite matching Perfect matching Disjoint paths Network connectivity Circulation problems Image segmentation Baseball elimination Project selection SummaryThe University of SydneyPage 901. 2. 3.4. 5.Max flow problemMin cut problemFord-Fulkerson:1. Residual graph 2. correctness3. complexityMax-Flow Min-Cut theorem Edmonds-Karp Appendix: Proof of Flow Value Lemma by Inductiontz f Flow conservationFlowvaluelemmacziven flow fffg fgf 174finfu FOHf sforetCA Pt by induction on IAIInductive case A I Let u c AksThe University of SydneyPage 91EquivWTSfwantf UtfAl u3 fin fat A fin Afat CA fo’t’CAl a3AlfiefinCA finCAcut A B fatCA fin Afztfzref fout EB finS3stoA 1243OInc in fin 4 11Increase in fo