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!
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 .
? 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