Analysis of Algorithms, I
CSOR W4231.002
Computer Science Department
Copyright By PowCoder代写 加微信 powcoder
Columbia University Network flows
1 Flow networks Applications
2 The residual graph and augmenting paths
3 The Ford-Fulkerson algorithm for max flow
4 Correctness of the Ford-Fulkerson algorithm
5 Application: max bipartite matching
1 Flow networks Applications
2 The residual graph and augmenting paths
3 The Ford-Fulkerson algorithm for max flow
4 Correctness of the Ford-Fulkerson algorithm
5 Application: max bipartite matching
Modeling transportation networks
Source: Communications of the ACM, Vol. 57, No. 8
Can model a fluid network or a highway system by a graph: edges carry traffic, nodes are switches where traffic gets diverted.
Flow networks
A flow network G = (V, E) is a directed graph such that
1. Every edge has a capacity ce ≥ 0. 2. Thereisasinglesources∈V.
3. Thereisasinglesinkt∈V.
A1: integer capacities A2: noedgeenterss A3: noedgeleavest
Two more assumptions for the purposes of the analysis
A4: If (u,v)∈E then (v,u)̸∈E.
A5: Everyv∈V −{s,t}isonsomes-tpath. Hence G has m ≥ n − 1 edges.
An example flow network
Given a flow network G, an s-t flow f in G is a function f : E → R+.
Intuitively, the flow f(e) on edge e is the amount of traffic that edge e carries.
Two kinds of constraints that every flow must satisfy
1. Capacity constraints: for all e ∈ E, 0 ≤ f(e) ≤ ce. 2. Flow conservation: for all v ∈ V − {s, t},
f(u,v)= f(v,w) (1) (u,v)∈E (v,w)∈E
In words, the flow into node v equals the flow out of v, or
f(e)= f(e) e into v e out of v
A cleaner equation for flow conservation constraints
1. fout(v)= f(e)
e out of v 2.fin(v)= f(e)
So we can rewrite equation (1) as: for all v ∈ V − {s, t}
fin(v) = fout(v) (2)
The value of a flow
Definition 1.
The value of a flow f, denoted by |f|, is
|f| = f(e) = fout(s)
e out of s
Exercise: show that |f| = fin(t).
An example flow of value 20
A flow f of value 20.
A flow of value 30
10/10 10/30 t
A (max) flow of value 30.
Max flow problem
Input: (G, s, t, c) such that
G = (V,E) is a flow network;
s, t ∈ V are the source and sink respectively; c is the (integer-valued) capacity function.
Output: a flow of maximum possible value
s-t cuts in flow networks
Definition 2.
An s-t cut (S, T ) in G is a bipartition of the vertices into two sets S and T , such that s ∈ S and t ∈ T .
A natural upper bound for the max value of a flow
Flow f must cross (S,T) to go from source s to sink t.
So it uses some (at most all) of the capacity of the edges
crossing from S to T.
So, intuitively, the value of the flow cannot exceed
ce e out of S
Max flow and min cut
Definition 3.
The capacity c(S,T) of an s-t cut (S,T) is defined as c(S,T) = ce.
e out of S
△ Note asymmetry in the definition of c(S, T )!
So, intuitively, the value of the max flow is upper bounded by
the capacity of every cut in the flow network, that is,
max|f| ≤ min c(S,T) (3)
(S,T) cut in G
Applications of max-flow and min-cut
Find a set of edges of smallest capacity whose deletion disconnects the network (min cut)
Bipartite matching (max flow) —coming up
Airline scheduling (max flow)
Baseball elimination (max flow)
Distribution of goods to cities (max flow)
Image segmentation (min cut)
Survey design (max flow)
1 Flow networks Applications
2 The residual graph and augmenting paths
3 The Ford-Fulkerson algorithm for max flow
4 Correctness of the Ford-Fulkerson algorithm
5 Application: max bipartite matching
“Undoing” flow
A flow f of value 20.
Goal: undo 10 units of flow along (u, v), divert it along (u, t).
Pushing flow back
s 10/20 10/10
10/10 10/30 t
“Push back” 10 units of flow along (v, u).
Send 10 more units from s to t along the green path edges
(s, v), (v, u), (u, t).
New flow f′ (on the right) with value 30.
Pushing flow forward and backward
By pushing flow back on (v, u), we created an s-t path on which we are pushing flow
forward, on edges with leftover capacity (e.g, (s, v));
backward, on edges that are already carrying flow so as to divert it to a different direction (e.g., (u, v)).
The residual graph Gf
Definition 4.
Given flow network G and flow f, the residual graph Gf has
the same vertices as G;
foreveryedgee=(u,v)∈Ewithf(e)
SoGf has≤2medgesandeverye∈Gf hascf(e)>0.
Example residual graph
20/20 0/20 20 20
s 20/30 t s 20 10 t
0/10 20/20 10 20 vv
Left: a graph G and a flow f of value 20.
Right: the residual graph Gf for flow network G and flow f.
The residual graph Gf as a roadmap for augmenting f
1. Let P be a simple s-t path in Gf.
2. Augment f by pushing extra flow on P .
Question: How much flow can we push on P without violating capacity constraints in Gf ?
The residual graph Gf as a roadmap for augmenting f
1. Let P be a simple s-t path in Gf.
2. Augment f by pushing extra flow on P .
Question: How much flow can we push on P without violating capacity constraints in Gf ?
Definition 5.
The bottleneck capacity c(P) of a simple path P is the minimum residual capacity of any edge of P. In symbols
c(P ) = min cf (e). e∈P
The residual graph Gf as a roadmap for augmenting f
1. Let P be a simple s-t path in Gf.
2. Augment f by pushing extra flow on P .
Question: How much flow can we push on P without violating capacity constraints in Gf ?
Definition 5.
The bottleneck capacity c(P) of a simple path P is the minimum residual capacity of any edge of P. In symbols
c(P ) = min cf (e). e∈P
Answer: The max amount of flow we can safely push on every edge of P is c(P).
The augmented flow f′
Let P be an augmenting path in the residual graph Gf . We obtain an augmented flow f′ as follows:
1. Foraforwardedgee∈P,setf′(e)=f(e)+c(P)
2. Forabackwardedgeer =(u,v)∈P,lete=(v,u)∈G;
set f′(e) = f(e) − c(P)
3. Fore∈EbutnotinP,f′(e)=f(e).
f′ is a flow.
Pseudocode for subroutine Augment
Input: a flow f, and an augmenting path P in Gf Output: the augmented flow f′
Augment(f, P )
foreachedge(u,v)∈P do
if e = (u, v) is a forward edge then
f(e) = f(e) + c(P) else
f (v, u) = f (v, u) − c(P ) end if
1 Flow networks Applications
2 The residual graph and augmenting paths
3 The Ford-Fulkerson algorithm for max flow
4 Correctness of the Ford-Fulkerson algorithm
5 Application: max bipartite matching
The Ford-Fulkerson algorithm
Ford-Fulkerson(G = (V, E, c), s, t)
for all e ∈ E do f(e) = 0
while there is an s-t path in Gf do
Let P be a simple s-t path in Gf f′ = Augment(f,P)
Set f = f′
SetGf =Gf′
Running time analysis
The algorithm terminates if the following facts are both true. Fact 6.
Every iteration of the while loop returns a flow increased by an integer amount.
There is a finite upper bound to the flow.
Running time analysis
The algorithm terminates if the following facts are both true. Fact 6.
Every iteration of the while loop returns a flow increased by an integer amount.
There is a finite upper bound to the flow.
Proof of Fact 7.
Let U be the largest edge capacity, that is, U = max ce. Then e
|f| ≤ ce ≤ nU. e out of s
f increases by an integer amount after Augment(f, P )
Proof of Fact 6.
It follows from the following claims.
During execution of the Ford-Fulkerson algorithm, the flow values {f(e)} and the residual capacities in Gf are all integers.
Letf beaflowinGandP asimples-tpathinGf with residual capacity c(P ) > 0. Then after Augment(f, P )
|f′| = |f| + c(P) ≥ |f| + 1.
f increases by an integer amount after Augment(f, P )
Proof of Claim 3.
Recall that |f| = fout(s).
1. Since P is an s-t path, it contains some edge out of s,
say (s, u).
2. Since P is simple, it does not contain any edge entering s
(P is in Gf , where there could be edges entering s!).
3. Since no edge enters s in G, (s,u) is a forward edge in Gf,
thus its augmented flow is f (s, u) + c(P ) ≥ f (s, u) + 1.
4. Since no other edge going out of s is updated, it follows
that the value of f′ is
|f′| = |f| + c(P) ≥ |f| + 1.
Running time of Ford-Fulkerson
1. Claim 3 guarantees at most nU iterations.
2. The running time of each iteration is bounded as follows:
O(m + n) to create Gf using adjacency list representation.
O(m + n) to run BFS or DFS to find the augmenting path.
O(n) for Augment(f, P ) since P has at most n − 1 edges.
⇒ Hence one iteration requires O(m) time. The running time of Ford-Fulkerson is O(mnU).
Definition 8 (Pseudo-polynomial algorithms).
An algorithm is pseudo-polynomial if it is polynomial in the size of the input when the numeric part of the input is encoded in unary.
Ford-Fulkerson is a pseudo-polynomial time algorithm.
Problems with pseudo-polynomial running times
1000000 v 1000000
Improved algorithms
FF can be made polynomial: use BFS instead of DFS Edmonds-Karp: O(nm2), Dinitz: O(n2m),
other improvements: O(nm log n), O(n3)
Unit capacities: O(min{m3/2, mn2/3}) [EvenTarjan1975]
Improved for sparse graphs: O ̃(m10/7) [Madry2013]
Integralcapacities:O(min{m3/2,mn2/3)log(n2/m)logU) [GoldbergRao1998]√
Improved: O ̃(m n log2 U) [LeeSidfort2014];
also improves for dense graphs with unit capacities
Realcapacities:O(nmlog(n2/m)) Improved: O(nm) [Orlin2013]
1 Flow networks Applications
2 The residual graph and augmenting paths
3 The Ford-Fulkerson algorithm for max flow
4 Correctness of the Ford-Fulkerson algorithm
5 Application: max bipartite matching
A natural upper bound for the max value of a flow
Ans-tcut(S,T)inGisabipartitionoftheverticesinto two sets S and T, such that s ∈ S and t ∈ T.
The capacity c(S,T) of s-t cut (S,T) is
e out of S
Then intuitively
max|f| ≤ min c(S,T) f (S,T) cut in G
Roadmap for proving optimality of Ford- that |f| = fout(s). We will prove the following.
1. For any flow f, the value of the flow |f| cannot exceed the
capacity of any cut in G.
2. Let f be the flow upon termination of the Ford-Fulkerson algorithm. We will exhibit a specific cut (S∗, T ∗) such that the value of f equals the capacity of (S∗, T ∗). In symbols,
|f| = c(S∗,T∗)
From 1., 2., we can conclude that f is a maximum flow. And(S∗,T∗)isacutofminimumcapacity.
Ford-Fulkerson terminates when ̸ ∃ s-t path in Gf
Consider the residual graph Gf upon termination of the algorithm. Let (S∗, T ∗) be the cut in Gf where
S∗ is the set of nodes reachable from the source s; T∗ contains every other node.
Is (S∗,T∗) also a cut in G?
On the cut (S∗,T∗)
1. (S∗,T∗)isans-tcut: thatis,s∈S∗,t∈T∗. Why?
2. In Gf, no edge crosses from S∗ to T∗. Why?
3. Hence,ife=(x,y)∈Ewithx∈S∗ andy∈T∗,then f(e) = ce (thus e ̸∈ Ef).
4. Similarly, if e′ = (u,v) ∈ E with u ∈ T∗ and v ∈ S∗, then f(e′) = 0. Why?
On the cut (S∗,T∗)
1. (S∗,T∗)isans-tcut: thatis,s∈S∗,t∈T∗. Why? Because there is no s-t path in Gf .
2. In Gf, no edge crosses from S∗ to T∗. Why?
If (u,v) crosses from S∗ to T∗, thus u ∈ S∗,v ∈ T∗, then ∃
s-v path in Gf . Hence v ∈ S∗; contradiction.
3. Hence,ife=(x,y)∈Ewithx∈S∗ andy∈T∗,then
f(e) = ce (thus e ̸∈ Ef).
4. Similarly, if e′ = (u,v) ∈ E with u ∈ T∗ and v ∈ S∗, then
f(e′) = 0. Why?
If f(e′) > 0, then (v,u) ∈ Ef, with cf(v,u) = f(e′) > 0. Contradicts our second observation.
Our observations on (S∗, T ∗) in a diagram
In G, every edge e crossing from S* to T* satisfies
f(e)=ce (of course, such e does not appear in Gf).
Every edge e′ in G crossing from T* to S* satisfies f(e′)=0.
f(e1)=ce1 f(e2)=ce2
Net flow across a cut
Definition 9.
The net flow across an s-t cut (S, T ) is the amount of flow leaving the cut minus the amount of flow entering the cut
fout(S) − fin(S), (5) 1. fout(S)= f(e)
2. fin(S)=
e out of S
f(e) e into S
Net flow across (S∗, T ∗) equals capacity of (S∗, T ∗)
f(e1)=ce1 f(e2)=ce2
fout(S∗) − fin(S∗) = f(e) − e out of S∗
= ce−0 e out of S∗
= c(S∗,T∗)
f(e) e into S∗
Roadmap revisited
Let f be the flow upon termination of the Ford-Fulkerson algorithm.
1. Exhibit a specific s-t cut (S∗, T ∗) in G such that the |f| = c(S∗,T∗).
Not quite there yet!
We exhibited (S∗,T∗) with net flow equal to its capacity.
We need to relate the net flow across (S∗,T∗) to |f|
(that is, the flow out of s).
In particular, if we showed them equal, then we’d have
|f| = c(S∗,T∗).
2. Show that |f| cannot exceed the capacity of any cut in G. 3. Conclude that f is a maximum flow.
net flow across any s-t cut = |f|
Recall that
fout(S)= f(e)
e out of S
fin(S)= f(e)
net flow across (S,T) fout(S)−fin(S)
Let f be any s-t flow, and (S,T) any s-t cut. Then |f| = fout(S) − fin(S).
Proof of Lemma 10
First, rewrite the flow out of s in terms of the flow on the vertices on S:
|f| = fout(s)=fout(v)−fin(v) (7) v∈S
fin(s)=0;
for every v ∈ S − {s}, the terms in the right-hand side of (7) cancel out because of flow conservation constraints.
Next, rewrite the right-hand side of equation 7 in terms of the edges that participate in these sums.
There are three types of edges.
Proof of Lemma 10 (cont’d)
1. Edges with both endpoints in S: such edges appear once in the first sum in equation 7 and once in the second, hence their flows cancel out.
2. Edges with the tail in S and head in T (out of S): such edges contribute to the first sum, fout(v), in equation 7
3. Edges with the tail in T and head in S (into S): such edges
so they appear with a +.
contribute to the second sum, fin(v), in equation 7 so
In effect, the right-hand side of equation 7 becomes
f(e)− f(e). e out of S e into S
they appear with a −.
The lemma follows.
The value of a flow cannot exceed capacity of any cut
Corollary 11.
Let f be any s-t flow and (S,T) any s-t cut. Then |f| ≤ c(S,T).
|f| = fout(S)−fin(S) ≤ fout(S) ≤ c(S,T).
Putting everything together
By Corollary 11, the value of a flow cannot exceed the capacity of any cut; in particular,
|f| ≤ c(S∗,T∗).
By Lemma 10, |f| equals the net flow across any s-t cut;
in particular,
|f| = fout(S∗) − fin(S∗).
From(6),thenetflowacross(S∗,T∗)equalsc(S∗,T∗).
Hence the above becomes
|f| = fout(S∗)−fin(S∗) = c(S∗,T∗).
⇒ Thus the flow computed by Ford-Fulkerson is a maximum flow because it cannot be increased anymore.
The max-flow min-cut theorem
Theorem 12.
If f is an s-t flow such that there is no s-t path in Gf, then there is an s-t cut (S∗,T∗) in G such that |f| = c(S∗,T∗). Therefore, f is a max flow and (S∗,T∗) is a cut of min capacity.
Theorem 13 (Max-flow Min-cut).
In every flow network, the maximum value of an s-t flow equals the minimum capacity of an s-t cut.
Integrality theorem
Recall the following claim.
During execution of the Ford-Fulkerson algorithm, the flow values {f(e)} and the residual capacities in Gf are all integers.
Combine with Theorem 12 to conclude:
Theorem 14 (Integrality theorem).
If all capacities in a flow network are integers, then there is a maximum flow for which every flow value f(e) is an integer.
1 Flow networks Applications
2 The residual graph and augmenting paths
3 The Ford-Fulkerson algorithm for max flow
4 Correctness of the Ford-Fulkerson algorithm
5 Application: max bipartite matching
Bipartite Matching
x1 y1 x1 y1
x2 y2 x2 y2
x3 y3 x3 y3
x4 y4 x4 y4
x5 y5 x5 y5 XYXY
Definition 15.
A matching M is a subset of edges where every vertex in X ∪ Y appears at most once.
Example: {(x1, y2), (x2, y3), (x3, y4), (x5, y5)} is a matching. Perfect matching: every vertex in X ∪ Y appears exactly once.
Not always possible: e.g., |X| ≠ |Y |. Maximum matching still desirable in applications.
If we had an algorithm to find maximum matching then we could also find a perfect matching, if one exists (why?).
Finding maximum matchings in bipartite graphs
Idea: Use the Ford-Fulkerson algorithm to find maximum (or perfect) matchings in bipartite graphs.
Strategy: reformulate the problem as a max flow problem which we know how to solve (reduction).
To this end, we need to transform our input bipartite graph into a flow network.
A diagram of the algorithm for max bipartite matching
Algorithm for max bipartite matching
Reduction R
Ford-Fulkerson
bipartite G
input to max bipartite matching
input to MaxFlow
Transform G into a flow network G’ = R(G)
max |f| = k
1. The reduction R must be efficient (polynomial in the size of G).
2. G and G′ should be equivalent, in the sense that G has a max matching of size k if and only if the max flow in G′ has value k.
Deriving a flow network given a bipartite graph
Given a bipartite graph G = (X ∪ Y, E), we construct a flow network G′ as follows.
Add a source s.
Addasinkt.
Add(s,x)edgesforallx∈X.
Add(y,t)edgesforally∈Y.
Directalle∈EfromXtoY.
Assign to every edge capacity of 1.
The flow network for the example bipartite graph
x5 y5 XY
Computing matchings in G from flows in G′
G=(X∪Y,E)isthebipartitegraph G′ is the derived flow network
The size of the maximum matching in G equals the value of the maximum flow in G′. The edges of the matching are the edges that carry flow from X to Y in G′.
Proof of Claim 5
The claim follows if we show the following two statements (why?).
1. (⇒ Forward direction) For any matching M in G, we can construct a flow f in G′ with value equal to the size of M, that is, |f| = |M|.
2. (⇐ Reverse direction) Given a max flow f′ in G′, we can construct a matching M′ in G, with size equal to the value of the max flow, that is, |M′| = |f′|.
(1.⇒)FromamatchingM toaflowf with|f|=|M|
Let |M| = k.
Gx1 y1 G′ x1 y1 ce=1
x2 y2 x2 y2
x3 y3 s x3 y3 t x4 y4 x4 y4
x5 y5 x5 y5 XYXY
Given matching M (the red edges in G), construct an integral flow f in G′, such that the value of f equals the number of edges in M.
(1.⇒)FromamatchingM toaflowf with|f|=|M|
Let |M| = k. Send one unit of flow along each of the k edge-disjoint s-t paths that use the edges in M; then |f| = k.
x50/1y5 XYXY
x2 1/1 1/1 0/1
s x31/1 y3 t
0/1×40/1 y4 0/1
Given matching M (the red edges in G), construct the integral flow f in G′. Then the value of f equals the number of edges in M.
(2. ⇐) From max flow f′ to M′ with |M′| = |f′|
y1 Gx1 y1 0/1
x2 1/1 1/1 0/1
y2 1/1 1/1
x5 y5 XY
x31/1 x4 0/1
Given integral max flow f′ in G′, construct a matching M′ in G so that the number of edges in M′ equals the value of f′.
From max flow f′ to matching M′ with |M′| = |f′|
Givenamaxflowf′ inG′ with|f′|=k,wewanttoselectaset of edges M′ in G so that M′ is a matching of size k.
By the integrality theorem, there is an integer-valued flow f of value k.
Then for every edge e, f(e) = 0 or f(e) = 1 (why?). Define the following matching M′:
M′ =e=(x,y):x∈X,y∈Y andf(e)=1.
Obtaining a matching M′ from an integral flow f
y1 Gx1 y1 0/1
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com