[SOLVED] CS AI ER algorithm Lecture 9

Lecture 9
Flow networks II:
Applications
The University of Sydney
Page 1

General techniques in this course
Greedy algorithms [Lecture 3]
Divide & Conquer algorithms [Lectures 4 & 5]
Dynamic programming algorithms [Lectures 6 and 7] Network flow algorithms [Lecture 8 and today]
Theory [Lecture 8]
Applications [today]
Lecture 10: NP and intractability
Lecture 11: Coping with hardness 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 3
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 4

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 5

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 6

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 7

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
Value = 6 + 0 + 8 1 + 11 = 24 Page 8
The University of Sydney
4 30 7

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 92 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 11 Recap: Residual Graph Originaledge: e=(u,v) IE. Flowf(e),capacityc(e). Residualedge. “Undo”flowsent. e=(u,v)andeR =(v,u). Residualcapacity:c(e)=iic(e)-f(e) ifeIEf i f (e) if eR I E Residual graph: Gf = (V, Ef ). Residualedgeswithpositiveresidualcapacity. Ef ={e:f(e) 0}.
capacity
u 17 v
6
flow
residualcapacity
u 11 v
6
residual capacity
The University of Sydney
Page 12

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 13
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 14

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 15

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]
Integrality. 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 16

Recap: Running Times
Theorem. Ford-Fulkerson runs in O(mF) time.
Theorem. FordFulkerson with maximum bottleneck augmenting path finds a max flow in O(m2 log F) time. [Covered in last weeks slides]
Theorem. FordFulkerson 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]
The University of Sydney Page 17

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 18

Reduction
Problem A
The University of Sydney Page 19
Problem B
Algorithm B
Solution A
Solution B

Reduction to Max Flows
Max Flow Problem
Max Flow Algorithm
The University of Sydney
Max Flow Solution
Page 20
Problem A
Solution A

7.5 Bipartite Matching
The University of Sydney Page 21

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 22

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 23

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 25

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 26

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 27

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 28

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 29
Matching
M = edges from L to R with f(e) = 1
Max flow f

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
(Equivalence) Max cardinality matching in G U value of max flow in G. The University of Sydney Page 30

Bipartite Matching: Proof of Correctness
Theorem: Max cardinality matching in G U value of max flow in G. Proof:
Assume 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.
1 1 1
2 2 12 21
G3 3s33tG 4 4 4 4
1 1
The Univers5ity of Sydney 5 5 5 Page 31

Bipartite Matching: Proof of Correctness
Theorem: Max cardinality matching in G U value of max flow in G. Proof: U
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: considercut(LEs,REt)
1 1 1
2 2 12 21
G3 3s33tG 4 4 4 4
1 1
The Univers5ity of Sydney 5 5 5 Page 32

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 33
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 34

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 will use max-flow min-cut to answer these questions The University of Sydney
Page 35

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 36

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 37

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
Page38

Proof of Marriage Theorem
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 59
The University of Sydney
foreground background
i2A
(i,j)neighbors:i2A,j2B

Image Segmentation: Problem
Foreground / background segmentation.
Label each pixel as belonging to foreground or background.
ai 3 0 is likelihood pixel i in foreground.
bi 3 0 is likelihood pixel i in background.
For neighboring pixels i and j, pij 3 0 is separation penalty for giving them different labels.
Goals:
Accuracy: if ai > 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 60
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 62
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 63
=
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
The University of Sydney
j2B i2A (i,j)neighbors:i2A,j2B
Page 64
=
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
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 65

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 66

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

Appendix
The University of Sydney Page 68

Proof of Marriage Theorem
Proof: U Suppose G does not have a perfect matching (flow 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
Page74
LA = {2,4,5,2,5} N(LA) = {2,5}

Proof of Marriage Theorem
Proof: U Suppose G does not have a perfect matching (flow