CSC373Week 5: Dynamic Programming (contd)Network Flow (start)
373W22 1
Karan Singh, Nathan Wiebe
*slides adapted from Nisarg Shah
Recap
373W22 2
• Some more DP
 Traveling salesman problem (TSP)
• Start of network flow
 Problem statement
 Ford-Fulkerson algorithm
 Running time
 Correctness using max-flow, min-cut
This Lecture
373W22 3
• Network flow in polynomial time
 Edmonds-Karp algorithm (shortest augmenting path)
• Applications of network flow
 Bipartite matching & Hall’s theorem
 Edge-disjoint paths & Menger’s theorem
 Multiple sources/sinks
 Circulation networks
 Lower bounds on flows
 Survey design
 Image segmentation
Ford-Fulkerson Recap
373W22 4
• Define the residual graph of flow
 has the same vertices as
 For each edge e = (, ) in , has at most two edges
o Forward edge = (, ) with capacity −
• We can send this much additional flow on
o Reverse edge = (,) with capacity ()
• The maximum “reverse” flow we can send is the maximum amount by which we can
reduce flow on , which is ()
o We only add each edge if its capacity > 0
Ford-Fulkerson Recap
373W22 5
• Example!
s t
u
v
20/20 20/3020/200/10
0/10
s t
u
v





Flow Residual graph
Ford-Fulkerson Recap
373W22 6
MaxFlow():
// initialize:
Set = 0 for all in
// while there is an - path in :
While = FindPath(s, t,Residual(, ))!=None:
= Augment(,)
UpdateResidual(,)
EndWhile
Return
Ford-Fulkerson Recap
373W22 7
• Running time:
 #Augmentations:
o At every step, flow and capacities remain integers
o For path in , bottleneck , > 0 implies bottleneck , ≥ 1
o Each augmentation increases flow by at least 1
o At most = ∑ leaving () augmentations
 Time for an augmentation:
o has vertices and at most 2 edges
o Finding an - path in takes ( + ) time
 Total time: ( + ⋅ )
Edmonds-Karp Algorithm
373W22 8
• At every step, find the shortest path from to in , and
augment.
MaxFlow():
// initialize:
Set = 0 for all in
// Find shortest - path in & augment:
While = BFS(s, t,Residual(, ))!=None:
= Augment(,)
UpdateResidual(,)
EndWhile
Return
Minimum number of edges
Proof
373W22 9
• () = shortest distance of from in residual graph
• Lemma 1: During the execution of the algorithm, () does
not decrease for any .
• Proof:
 Suppose augmentation → decreases () for some
 Choose the with the smallest in ′
o Say = in ′, so ≥ + 1 in
 Look at node just before on a shortest path → in ′
o = − 1 in ′
o () didn’t decrease, so ≤ − 1 in
• () = shortest distance of from in residual graph
• Lemma 1: During the execution of the algorithm, () does
not decrease for any .
• Proof:
Proof
373W22 10
() ()

′
≤ − 1
− 1
≥ + 1

• In , (, ) must be missing
• We must have added (, ) by
selecting (,) in augmenting path
• But is a shortest path, so it cannot
have edge , with >
Proof
373W22 11
• Call edge (, ) critical in an augmentation step if
 It’s part of the augmenting path and its capacity is equal to bottleneck(, )
 Augmentation step removes and adds (if missing)
• Lemma 2: Between any two steps in which (, ) is critical,
() increases by at least 2
• Proof of Edmonds-Karp running time
 Each () can go from 0 to (Lemma 1)
 So, each edge (, ) can be critical at most /2 times (Lemma 2)
 So, there can be at most ⋅ /2 augmentation steps
 Each augmentation takes () time to perform
 Hence, 2 operations in total!
Proof
373W22 12
• Lemma 2: Between any two steps in which (, ) is critical,
() increases by at least 2
• Proof:
 Suppose (, ) was critical in
o So, the augmentation step must have removed it
 Let = () in
o Because , is part of a shortest path, = + 1 in
 For (, ) to be critical again, it must be added back at some point
o Suppose ′ → ′′ steps adds it back
o Augmenting path in must have selected (,)
o In ′: = + 1 ≥ + 1 + 1 = + 2
Lemma 1 on
Edmonds-Karp Proof Overview
373W22 13
• Note:
 Some graphs require Ω() augmentation steps
 But we may be able to reduce the time to run each augmentation
step
• Two algorithms use this idea to reduce run time
 Dinitz’s algorithm [1970] ⇒(2)
 Sleator–Tarjan algorithm [1983] ⇒( log)
o Using the dynamic trees data structure
373W22 14
Network Flow Applications
373W22 15
Rail network connecting Soviet Union with Eastern European countries
(Tolstoǐ 1930s)
373W22 16
Rail network connecting Soviet Union with Eastern European countries
(Tolstoǐ 1930s)
Min-cut
Integrality Theorem
373W22 17
• Before we look at applications, we need the following special property of the
max-flow computed by Ford-Fulkerson and its variants
• Observation:
 If edge capacities are integers, then the max-flow computed by Ford-Fulkerson and its variants
are also integral (i.e., the flow on each edge is an integer).
 Easy to check that each augmentation step preserves integral flow
Bipartite Matching
373W22 18
• Problem
 Given a bipartite graph = ( ∪ ,), find a maximum cardinality matching
• We do not know any efficient greedy or dynamic programming algorithm for this
problem.
• But it can be reduced to max-flow.
Bipartite Matching
373W22 19
• Create a directed flow graph where we…
 Add a source node and target node
 Add edges, all of capacity 1:
o → for each ∈ , → for each ∈
o → for each , ∈

Bipartite Matching
373W22 20
• Observation
 There is a 1-1 correspondence between matchings of size in the original graph and flows
with value in the corresponding flow network.
• Proof: (matching ⇒ integral flow)
 Take a matching = 1, 1 , … , , of size
 Construct the corresponding unique flow where…
o Edges → , → , and → have flow 1, for all = 1, … ,
o The rest of the edges have flow 0
 This flow has value
Bipartite Matching
373W22 21
• Observation
 There is a 1-1 correspondence between matchings of size in the original graph and flows
with value in the corresponding flow network.
• Proof: (integral flow ⇒ matching)
 Take any flow with value
 The corresponding unique matching = set of edges from to with a flow of 1
o Since flow of comes out of , unit flow must go to distinct vertices in
o From each such vertex in , unit flow goes to a distinct vertex in
o Uses integrality theorem
Bipartite Matching
373W22 22
• Perfect matching = flow with value
 where = =
• Recall naïve Ford-Fulkerson running time:
 (( + ) ⋅ ), where = sum of capacities of edges leaving
 Q: What’s the runtime when used for bipartite matching?
• Some variants are faster…
 Dinitz’s algorithm runs in time when all edge capacities are 1
Hall’s Marriage Theorem
373W22 23
• When does a bipartite graph have a perfect matching?
 Well, when the corresponding flow network has value
 But can we interpret this condition in terms of edges of the original
bipartite graph?
 For ⊆ , let ⊆ be the set of all nodes in adjacent to some
node in
• Observation:
 If has a perfect matching, ≥ || for each ⊆
 Because each node in must be matched to a distinct node in ()
Hall’s Marriage Theorem
373W22 24
• We’ll consider a slightly different flow network, which is still
equivalent to bipartite matching
 All → edges now have ∞ capacity
 → and → edges are still unit capacity

∞
∞
1
1 1
1
Hall’s Marriage Theorem
373W22 25
• Hall’s Theorem:
 has a perfect matching iff ≥ || for each ⊆
• Proof (reverse direction, via network flow):
 Suppose doesn’t have a perfect matching
 Hence, max-flow = min-cut <
 Let (,) be the min-cut
o Can’t have any → (∞ capacity edges)
o Has unit capacity edges → ∩ and ∩ →
Hall’s Marriage Theorem
373W22 26
• Hall’s Theorem:
 has a perfect matching iff ≥ || for each ⊆
• Proof (reverse direction, via network flow):
 , = ∩ + ∩ < =
 So ∩ < | ∩ |
 But ∩ ⊆ ∩ because the cut doesn’t include any ∞ edges
 So ∩ ≤ ∩ < | ∩ |. ∎
Some Notes
373W22 27
• Runtime for bipartite perfect matching
 1955: () → Ford-Fulkerson
 1973: → blocking flow (Hopcroft-Karp, Karzanov)
 2004: 2.378 → fast matrix multiplication (Mucha–Sankowsi)
 2013: � ⁄10 7 → electrical flow (Mądry)
 Best running time is still an open question
• Nonbipartite graphs
 Hall’s theorem → Tutte’s theorem
 1965: (4) → Blossom algorithm (Edmonds)
 1980/1994: → Micali-Vazirani
Edge-Disjoint Paths
373W22 28
• Problem
 Given a directed graph = (,), two nodes and , find the maximum number of edge-
disjoint → paths
 Two → paths and are edge-disjoint if they don’t share an edge
Edge-Disjoint Paths
373W22 29
• Application:
 Communication networks
• Max-flow formulation
 Assign unit capacity on all edges
Edge-Disjoint Paths
373W22 30
• Theorem:
 There is 1-1 correspondence between sets of edge-disjoint → paths and integral flows of
value
• Proof (paths → flow)
 Let 1, … , be a set of edge-disjoint → paths
 Define flow where = 1 whenever ∈ for some , and 0 otherwise
 Since paths are edge-disjoint, flow conservation and capacity constraints are satisfied
 Unique integral flow of value
Edge-Disjoint Paths
373W22 31
• Theorem:
 There is 1-1 correspondence between edge-disjoint → paths and integral flows of value
• Proof (flow → paths)
 Let be an integral flow of value
 outgoing edges from have unit flow
 Pick one such edge (,1)
o By flow conservation, 1 must have unit outgoing flow (which we haven’t used up yet).
o Pick such an edge and continue building a path until you hit
 Repeat this for the other − 1 edges from with unit flow ∎
Edge-Disjoint Paths
373W22 32
• Maximum number of edge-disjoint → paths
 Equals max flow in this network
 By max-flow min-cut theorem, also equals minimum cut
 Exercise: minimum cut = minimum number of edges we need to delete to disconnect from
o Hint: Show each direction separately (≤ and ≥)
Edge-Disjoint Paths
373W22 33
• Exercise!
 Show that to compute the maximum number of edge-disjoint - paths in an undirected graph,
you can create a directed flow network by adding each undirected edge in both directions and
setting all capacities to 1
• Menger’s Theorem
 In any directed/undirected graph, the maximum number of edge-disjoint (resp. vertex-disjoint)
→ paths equals the minimum number of edges (resp. vertices) whose removal disconnects
and
Multiple Sources/Sinks
373W22 34
• Problem
 Given a directed graph = (,) with edge capacities : → ℕ, sources 1, … , and sinks
1, … , ℓ, find the maximum total flow from sources to sinks.
Multiple Sources/Sinks
373W22 35
• Network flow formulation
 Add a new source , edges from to each with ∞ capacity
 Add a new sink , edges from each to with ∞ capacity
 Find max-flow from to
 Claim: 1 − 1 correspondence between flows in two networks
Circulation
373W22 36
• Input
 Directed graph = (,)
 Edge capacities ∶ → ℕ
 Node demands ∶ → ℤ
• Output
 Some circulation ∶ → ℕ satisfying
o For each ∈ : 0 ≤ ≤ ()
o For each ∈ : ∑ entering () − ∑ leaving = ()
 Note that you need ∑: >0 () = ∑: <0−()
 What are demands?
Circulation
373W22 37
• Demand at = amount of flow you need to take out at node
 > 0 : You need to take some flow out at
o So, there should be () more incoming flow than outgoing flow
o “Demand node”
 < 0 : You need to put some flow in at
o So, there should be more outgoing flow than incoming flow
o “Supply node”
 = 0 : Node has flow conservation
o Equal incoming and outgoing flows
o “Transshipment node”
Circulation
373W22 38
• Example
Circulation
373W22 39
• Network-flow formulation
 Add a new source and a new sink
 For each “supply” node with < 0, add edge (, ) with capacity −()
 For each “demand” node with > 0, add edge (, ) with capacity ()
• Claim:
 has a circulation iff has max flow of value
�
: >0 =�: <0−()
Circulation
373W22 40
• Example
Circulation
373W22 41
• Example
Circulation with Lower Bounds
373W22 42
• Input
 Directed graph = (,)
 Edge capacities ∶ → ℕ and lower bounds ℓ ∶ → ℕ
 Node demands ∶ → ℤ
• Output
 Some circulation ∶ → ℕ satisfying
o For each ∈ : ℓ() ≤ ≤ ()
o For each ∈ : ∑ entering () − ∑ leaving = ()
 Note that you still need ∑: >0 () = ∑: <0−()
Circulation with Lower Bounds
373W22 43
• Transform to circulation without lower bounds
 Do the following operation to each edge
• Claim: Circulation in iff circulation in
 Proof sketch: () gives a valid circulation in iff − ℓ() gives a valid circulation in
Survey Design
373W22 44
• Problem
 We want to design a survey about products
o We have one question in mind for each product
o Need to ask product ’s question to between and ′ consumers
 There are a total of consumers
o Consumer owns a subset of products
o We can ask consumer questions about only these products
o We want to ask consumer between and ′ questions
 Is there a survey meeting all these requirements?
Survey Design
373W22 45
• Bipartite matching is a special case
 = ′ = = ′ = 1 for all and
• Formulate as circulation with lower bounds
 Create a network with special nodes and
 Edge from to each consumer with flow ∈ [ , ′]
 Edge from each consumer to each product ∈ with flow ∈ [0,1]
 Edge from each product to with flow ∈ [ ,′]
 Edge from to with flow in [0,∞]
 All demands and supplies are 0
Survey Design
373W22 46
• Max-flow formulation:
 Feasible survey iff feasible circulation in this network
Image Segmentation
373W22 47
• Foreground/background segmentation
 Given an image, separate “foreground” from “background”
• Here’s the power of PowerPoint (or the lack thereof)
Remove
background
Image Segmentation
373W22 48
• Foreground/background segmentation
 Given an image, separate “foreground” from “background”
• Here’s what remove.bg gets using AI
Remove
background
Image Segmentation
373W22 49
• Informal problem
 Given an image (2D array of pixels), and likelihood estimates of different pixels being
foreground/background, label each
pixel as foreground or background
 Want to prevent having too many
neighboring pixels where one is
labeled foreground but the other
is labeled background
Image Segmentation
373W22 50
• Input
 An image (2D array of pixels)
 = likelihood of pixel being in foreground
 = likelihood of pixel being in background
 , = penalty for “separating” pixels and (i.e. labeling one of them
as foreground and the other as background)
• Output
 Label each pixel as “foreground” or “background”
 Minimize “total penalty”
o Want it to be high if is high but is labeled background, is high
but is labeled foreground, or , is high but and are separated
Image Segmentation
373W22 51
• Recall
 = likelihood of pixels being in foreground
 = likelihood of pixels being in background
 , = penalty for separating pixels and
 Let = pairs of neighboring pixels
• Output
 Minimize total penalty
o = set of pixels labeled foreground
o = set of pixels labeled background
o Penalty =
�
∈
+ �
∈
+ �
, ∈
∩ , =1
,
Image Segmentation
373W22 52
• Formulate as a min-cut problem
 Want to divide the set of pixels into (,) to minimize
�
∈
+ �
∈
+ �
, ∈
∩ , =1
,
 Nodes:
o source , target , and for each pixel
 Edges:
o (, ) with capacity for all
o ( , ) with capacity for all
o ( , ) and ( , ) with capacity , each for all neighboring (, )
Image Segmentation
373W22 53
• Formulate as min-cut problem
 Here’s what the network looks like
Image Segmentation
373W22 54
 Consider the min-cut (,)
, = �
∈
+ �
∈
+ �
, ∈
∈,∈
,
 Exactly what we want to minimize!
If and are labeled differently, it
will add , exactly once
Image Segmentation
373W22 55
• GrabCut [Rother-Kolmogorov-Blake 2004]
Profit Maximization (Yeaa…!)
373W22 56
• Problem
 There are tasks
 Performing task generates a profit of
o We allow < 0 (i.e., performing task may be costly)
 There is a set of precedence relations
o , ∈ indicates that if we perform , we must also perform
• Goal
 Find a subset of tasks which, subject to the precedence constraints, maximizes =
∑∈
Profit Maximization
373W22 57
• We can represent the input as a graph
 Nodes = tasks, node weights = profits,
 Edges = precedence constraints
 Goal: find a subset of nodes with highest total weight s.t. if ∈ and , ∈ , then ∈ as
well
-1
3
-4
-2
-3
7
3
-9
Profit Maximization
373W22 58
• Want to formulate as a min-cut
 Add source and target
 min-cut (,) ⇒ want desired solution to be = ∖ {}
 Goals:
o (,) should nicely relate to ()
o Precedence constraints must be respected
• “Hard” constraints are usually enforced using infinite capacity edges
• Construction:
 Add each , ∈ with infinite capacity
 For each :
o If > 0, add (, ) with capacity
o If < 0, add (, ) with capacity −
Profit Maximization
373W22 59
-2
3 -3
-17
3
0
Profit Maximization
373W22 60
-2
3 -3
-17
3
0
s
t
3
7
3
3
1
2
∞
∞
∞
∞
∞
∞
∞
∞
Profit Maximization
373W22 61
A possible cut
QUESTION: What is the capacity of this cut?
-2
3 -3
-17
3
0
s
t
3
7
3
3
1
2
∞
∞
∞
∞
∞
∞
∞
∞
Profit Maximization
373W22 62
Exercise: Show that…
1. A finite capacity cut exists.
2. If (,) is finite, then \ is a valid solution;
3. Minimizing (,) maximizes (\ )
• Show that , = constant − \ , where the
constant is independent of the choice of (,)

欢迎咨询51作业君