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 Î E: 0 £ f(e) £ c(e)
(capacity) (conservation)
å f (e) . e out of s
6
10
– For each v Î V – {s, t}: å f(e) = e in to v
– Definition: The value of a flow f is: 6
å 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)ofVwithsÎAandtÎB.
– The capacity of a cut (A, B) is: cap(A, B) = 295
å 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)ofVwithsÎAandtÎB.
– The capacity of a cut (A, B) is: cap(A, B) = 2 9 5
10
å 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.
åf(e) – åf(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)=0foralledgeeÎE.
– 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) ÎE. – Flowf(e),capacityc(e).– Residualedge.– “Undo”flowsent.– e=(u,v)andeR =(v,u). – Residualcapacity:c(e)=ìíc(e)-f(e) ifeÎEf î f (e) if eR Î E– Residual graph: Gf = (V, Ef ).– Residualedgeswithpositiveresidualcapacity. – Ef ={e:f(e)
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 Î 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) Î 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. Ford–Fulkerson with maximum bottleneck augmenting path finds a max flow in O(m2 log F) time. [Covered in last week’s slides]
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]
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 Í 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 È R, E).
– M Í 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 È R, E).
– M Í 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 È R È {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 2’1
G3 3’s33’tG’ 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 2’1
1 1′
G3 3’s33’t 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 Û value of max flow in G’. The University of Sydney Page 30
Bipartite Matching: Proof of Correctness
Theorem: Max cardinality matching in G Û 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 2’1
G3 3’s33’tG’ 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 Û value of max flow in G’. Proof: Ü
– LetfbeamaxflowinG’ofvaluek.
– 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(LÈs,RÈt)
1 1 1′
2 2′ 12 2’1
G3 3’s33’tG’ 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 Í 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 È R, E), has a perfect matching, then |N(S)| 3 |S| for all subsets S Í 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 È R, E), has a perfect matching, then |N(S)| 3 |S| for all subsets S Í 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 È R, E) be a bipartite graph with |L| = |R|. Then, G has a perfect matching iff |N(S)| 3 |S| for all subsets S Í 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: Ü Suppose G does not have a perfect matching (flow
– 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 Xai Xbj+
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 Xai Xbj+ 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 Xai Xbj+ 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: Ü Suppose G does not have a perfect matching (flow
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: Ü Suppose G does not have a perfect matching (flow
Reviews
There are no reviews yet.