编程代考 Analysis of Algorithms, I

Analysis of Algorithms, I
CSOR W4231.002

Computer Science Department

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

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)0,anedge er = (v,u) in Gf with residual capacity cf(er) = f(e) (backward edge).
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 ?
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 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.
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

Related Posts