[SOLVED] CS AI ER algorithm The University of Sydney

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

Lecture 7
Flow networks II:
Applications
The University of Sydney
Page 2

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

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

Recap: Max flow problem
Max flow problem. Find s-t flow of maximum value.
9
2 9 5
10
10
1
15 15 0
9
10
40 489
s 5 3 8 6 10 t
capacity
flow
15
14
4
40 6 150
14
10
10
The University of Sydney
4 30 7
Value = 2Pa8ge 6

Recap: Cuts
Definitions:
Ans-tcutisapartition(A,B)ofVwithsIAandtIB.
The capacity of a cut (A, B) is: cap(A, B) = 295
a c(e) e out of A
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 7

Recap: Cuts
Definitions:
Ans-tcutisapartition(A,B)ofVwithsIAandtIB.
The capacity of a cut (A, B) is: cap(A, B) = 2 9 5
10
a c(e) e out of A
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 8

Recap: 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.
af(e) af(e) = v(f) e out of A e in to 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
The University of Sydney
4 30 7
Value = 6 + 0 + 8 1 + 11 = 24 Page 9

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 as much flow as possible along path P. Repeat until you get stuck. 1 s s3 0 X0 2 0t t20 X02001010020X0 2 0Flow value = 20 The University of SydneyPage 102 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 1The path (s,2), (1,2), (1,t) is an augmenting path 1120 10 20 1020 10 20 10s 3010 t s 3010 t10 20 10 2010 20 10 2022TgherUeniverdsityof=Syd2ne0y opt = 30 Page 12 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 13
residualcapacity

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 15
The University of Sydney

Recap: 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 16

Recap: Ford-Fulkerson Algorithm
0
2 4 4
G:
0
1 0 X8 8
10208 6010
s 10 3 X 5 t 9 10
X
0 2 02 10X8
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 17

Recap: Max-Flow Min-Cut Theorem
Augmenting path theorem: Flow f is a max flow if and only if there are no augmenting paths in the residual graph.
Max-flow min-cut theorem: The value of the max flow is equal to the value of the min cut. [Ford-Fulkerson 1956]
The University of Sydney Page 18

Max-Flow Min-Cut Theorem
Augmenting path theorem: Flow f is a max flow if and only if there are no augmenting paths in the residual graph.
Max-flow min-cut theorem: The value of the max flow is equal to the value of the min cut. [Ford-Fulkerson 1956]
Integrality (today). If all capacities are integers then every flow value f(e) and every residual capacities cf (e) remains an integer throughout the algorithm.
The University of Sydney Page 19

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 20

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 21

Ford-Fulkerson: Running Time
Corollary:
Ford-Fulkerson runs in O((m+n)F) time, if all capacities are integers.
Proof: F 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 22

Running Times
Theorem. Ford-Fulkerson runs in O(mF) time.
Theorem. Ford-Fulkerson with maximum bottleneck augmenting path finds a max flow in O(m2 log F) time. [Edmonds-Karp, see Appendix]
Theorem. Ford-Fulkerson with shortest augmenting path finds a max flow in O(nm2) time. [3927 Lecture]
Theorem. There is an algorithm that finds a max flow in O(nm) time. [Orlin 2012]
Above algorithms return integral max flow when capacities are integers.
The University of Sydney Page 23

Applications of max flow
Bipartite matching
Perfect matching
Disjoint paths
Network connectivity Circulation problems Image segmentation Baseball elimination Project selection
The University of Sydney
Page 24

Reductions
A reduction from Problem X to Problem Y is an algorithm of the following form:
Algorithm for X
f(I)
Instance Solution of Y for f(I)
Transform instance of X to instance of Y
Algorithm for Y
Transform solution for Y to a solution for X
Instance of X
I
Solution for I
The University of Sydney
Page 25

Reduction to Max Flow
A reduction from Problem X to Max Flow is an algorithm of the following form:
Instance of X
I
Solution for I
Algorithm for X
Flow Network
G(I)
Max Flow of G(I)
Transform instance of X to instance of Y
Algorithm for Max Flow
Transform solution for Y to a solution for X
The University of Sydney
Page 26

7.5 Bipartite Matching
The University of Sydney Page 29

Matching
Input: undirected graph G = (V, E).
M I E is a matching if each node appears in at most one edge
in M.
Max matching: find a max cardinality matching.
The University of Sydney Page 30

Bipartite Matching
Input: undirected, bipartite graph G = (L E R, E).
M I E is a matching if each node appears in at most one edge
in M.
Max matching: find a max cardinality matching.
1 1 2 2
3 3 4 4
matching 1-2, 3-1, 4-5
5 5
The University of Sydney L
R Page 31

Bipartite Matching
Input: undirected, bipartite graph G = (L E R, E).
M I E is a matching if each node appears in at most one edge
in M.
Max matching: find a max cardinality matching.
1 1 2 2
3 3 4 4
max matching 1-1, 2-2, 3-3, 5-5
5 5
The University of Sydney L
R Page 33

Bipartite Matching: Reduction to Max Flow
Bipartite Matching Problem
Step 1: Max flow formulation
Step 2: Use a Max flow algo
Step 3: Extract max matching from max flow
Bipartite Matching Solution Max Flow Solution
Max Flow Problem
The University of Sydney
Page 34

Step 1: Max flow formulation
Max flow formulation.
Create digraph G = (L E R E {s, t}, E ).
Direct all edges from L to R, and assign unit capacity.
Add source s, and unit capacity edges from s to each node in L. Add sink t, and unit capacity edges from each node in R to t.
G
1
1 1 1 2 2
3 3 4 4
1
s
t
The University of Sydney
L 5 5 R
Page 35

Bipartite Matching: Reduction to Max Flow
Bipartite Matching Problem
Step 1: Max flow formulation
Step 2: Use a Max flow algo
Max Flow Solution
Max Flow Problem
Step 3: Extract matching from flow
Bipartite Matching Solution
The University of Sydney
Page 36

Step 3: Extract Matching from Flow
1 1 1
2 2 12 21
G3 3s33tG 4 4 4 4
5 5 5 5
1 1
The University of Sydney
Page 37
Matching
M = edges from L to R with f(e) = 1
Max flow f
By Integrality of Max Flow, there exists max flow such that each f(e) is 0 or 1.

Bipartite Matching: Proof of Correctness
1 1 1
2 2 12 21
1 1
G3 3s33t 4 4 4 4
5 5 5 5
G
Matching
M = edges from L to R with f(e) = 1
Max flow f
By Integrality of Max Flow, there exists max flow such that each f(e) is 0 or 1.
(Equivalence) Max cardinality matching in G U value of max flow in G. The University of Sydney Page 38

Bipartite Matching: Proof of Correctness
Theorem: Max cardinality matching in G = Max flow in G. Proof:
Suppose max matching M has cardinality k.
Consider a flow f that sends 1 unit along each of the k paths, defined by
the edges in M.
fisaflow,andithasvaluek.
Since M is matching, capacity constraints are satisfied
1 1 1
2 2 12 21
G3 3s33tG 4 4 4 4
1 1
The Univers5ity of Sydney 5 5 5 Page 39

Bipartite Matching: Proof of Correctness
Theorem: Max cardinality matching in G U Max flow in G. Proof:
LetfbeamaxflowinGofvaluek.
Integrality theorem k is integral so f(e) is 0 or 1. ConsiderM=setofedgesfromLtoRwithf(e)=1.
each node in L and R participates in at most one edge in M
|M| = k: consider cut (LE s, RE t) and use Flow Value Lemma
1 1 1
2 2 12 21
G3 3s33tG 4 4 4 4
1 1
The Univers5ity of Sydney 5 5 5 Page 40

Bipartite Matching: Running Time
Bipartite Matching Problem
Max Flow Problem
O(n)
Generic augmenting path: O(mF) = O(mn) Edmonds-Karp: O(m2 log F ) = O(m2 log n)
Bipartite Matching Solution
Max Flow Solution
The University of Sydney
Page 41
O(n)

Bipartite Matching: Running Time
Which max flow algorithm to use for bipartite matching? Generic augmenting path: O(mF) = O(mn).
Edmonds-Karp: O(m2 log F ) = O(m2 log n).
Best known: O(mn1/2). [Micali-Vazirani 1980]
Non-bipartite matching:
Structure of non-bipartite graphs is more complicated, but
well-understood.
Blossom algorithm: O(mn2).
[Tutte-Berge, Edmonds-Galai] [Edmonds 1965]
The University of Sydney
Page 42

Perfect Matching
Definition: A matching M I E is perfect if each node appears in exactly one edge in M.
Question: When does a bipartite graph have a perfect matching?
Structure of bipartite graphs with perfect matchings. Clearly we must have |L| = |R|.
What other conditions are necessary?
What conditions are sufficient?
We can use max-flow min-cut to answer these questions The University of Sydney
Page 43

Perfect Matching
Notation: Let S be a subset of nodes, and let N(S) be the set of nodes adjacent to nodes in S.
Observation. If a bipartite graph G = (L E R, E), has a perfect matching, then |N(S)| 3 |S| for all subsets S I L.
Proof: Each node in S has to be matched to a different node in N(S).
1 1
2 2
3 3
4 4
The University of Sydney L 5 5 R Page 44

Perfect Matching
Notation: Let S be a subset of nodes, and let N(S) be the set of nodes adjacent to nodes in S.
Observation. If a bipartite graph G = (L E R, E), has a perfect matching, then |N(S)| 3 |S| for all subsets S I L.
Proof: Each node in S has to be matched to a different node in N(S).
1 1
2 2
3 3
4 4
No perfect matching: S = { 2, 4, 5 }
N(S) = { 2, 5 }.
The University of Sydney L 5 5 R Page 45

Marriage Theorem
Marriage Theorem. Let G = (L E R, E) be a bipartite graph with |L| = |R|. Then, G has a perfect matching iff |N(S)| 3 |S| for all subsets S I L.
Proof: This was the previous observation.
1 1
2 2
3 3
4 4
No perfect matching: S = { 2, 4, 5 }
N(S) = { 2, 5 }.
The University of Sydney L 5 5 R
Page46

Proof of Marriage Theorem (See Appendix)
Proof: U Suppose G does not have a perfect matching (flow bi in isolation, prefer to label i in foreground.
Smoothness: if many neighbors of i are labeled foreground, we should
be inclined to label i as foreground. X Find partition (A, B) that maximizes:
ai +
X
j2B
bj
X
pij Page 62
The University of Sydney
foreground background
i2A
(i,j)neighbors:i2A,j2B

Image Segmentation
Turn into minimization problem. Maximizing
X ai + X bj X pij i2A j2B (i,j)neighbors:i2A,j2B
is equivalent to minimizing
ai bj + pij
The University of Sydney
Page 64
XX!X
i2A j2B (i,j)neighbors:i2A,j2B = Xai+bi XaiXbj+
X p i i2A j2B (i,j)neighbors:i2A,j2B
= X aj X bi + j2B i2A
X pij (i,j)neighbors:i2A,j2B
i

Image Segmentation
Turn into minimization problem. Maximizing
X ai + X bj X pij i2A j2B (i,j)neighbors:i2A,j2B
i2A j2B (i,j)neighbors:i2A,j2B
is equivalent to minimizing
ai bj + pij
The University of Sydney
j2B i2A (i,j)neighbors:i2A,j2B
Page 65
=
j2B i2A aj + bi +
(i,j)neighbors:i2A,j2B pij
XX!X
Is equivalent to min!imizing
ai + bi Xai Xbj + X pij i = i2A aj j2B bi + (i,j)neighbors:i2A,j2Bpij
XXX
X p i i2A j2B (i,j)neighbors:i2A,j2B
= Xai+bi XaiXbj+ XXXX
i

Image Segmentation
Turn into minimization problem. Maximizing
X ai + X bj X pij i2A j2B (i,j)neighbors:i2A,j2B
i2A j2B (i,j)neighbors:i2A,j2B
is equivalent to minimizing
ai bj + pij
XX!X
Is equivalent to min!imizing
ai + bi Xai Xbj + X pij i = i2A aj j2B bi + (i,j)neighbors:i2A,j2Bpij
X p i i2A j2B (i,j)neighbors:i2A,j2B
= Xai+bi XaiXbj+ XXXX
XXX
The University of Sydney
j2B i2A (i,j)neighbors:i2A,j2B
Page 66
=
j2B i2A aj + bi +
(i,j)neighbors:i2A,j2B pij
i

Image Segmentation
Formulate as min cut problem.
pij pij
G = (V, E): vertices correspond to pixels pij
Add source to correspond to foreground; add sink to correspond to background
Two antiparallel edges between every pair i, j of neighboring pixels
aj
s ipijj t bi
G
The University of Sydney
Page 67

Image Segmentation
Consider min cut (A, B) in G.
A = foreground, B = background
if i and j on different sides, pij counted exactly once
cap(A, B) = X aj + X bi + X pij j2B i2A (i,j)neighbors:i2A,j2B
Precisely the quantity we want to minimize.
s
aj i pij
bi
j
t
A
G
The University of Sydney
Page 68

7.12 Baseball Elimination
Team i
Wins wi
Losses li
To play ri
Against = rij
Atl
Phi
NY
Mon
Atlanta
83
71
8

1
6
1
Philly
80
79
3
1

0
2
New York
78
78
6
6
0

0
Montreal
77
82
3
1
2
0

Which teams have a chance of finishing the season with most wins?
A team is said to be eliminated if no outcome of the remaining games results in the team finishing (or tying) with the most wins.
Montreal eliminated since it can finish with at most 80 wins, and Atlanta already has 83.
wi +ri c(A,B) = |LCB|+|RCA| 3 n-|LA|+|N(LA)| |LA|> |N(LA)| 1 1
A
2 2 3 3
N(LA)
4 4
L 5 5 R
s
LA
t
The University of Sydney
Page85
LA = {2,4,5,2,5} N(LA) = {2,5}