Analysis of Algorithms
V. Adamchik CSCI 570 Lecture 8 University of Southern California
Network Flow
Reading: chapter 7
Violation of Academic Integrity
Honor Code Pledge: “I affirm that I have not used any unauthorized materials in completing this exam and have neither given assistance to others nor received assistance from others.“
There are significant consequences for violating academic integrity.
If you feel that you violate the pledge you signed, I want you to step forward and contact me directly by the end of this week.
The Network Flow Problem
Our fourth major algorithm design technique
(greedy, divide-and-conquer, and dynamic programming).
Plan:
The Ford-Fulkerson algorithm Max-Flow Min-Cut Theorem
The Flow Problem
source
Suppose you want to ship natural gas from Alaska to Texas.
Pipes have capacities.
The goal is to send as much gas as possible. How can you do it?
sink
The Max-Flow Problem
21 21531
t
s
32
The MAX Flow Problem
2a1 21531
s b
t
How can you see that the flow is really max?
32 The max-flow here is __.
Greedy Approach: push the max
u
s30 t
10 v
20
10
20
Push 20 via s-u-v-t
Canceling Flow
20 u 10
s 30 t
10 v
10
s 10 t 10 v
20
Residual Graph Gf
G
Flow 6
u Cap10 v
Gf
Cap 4
uv
Cap 6
Example: residual graph
a2b
3
3G
1 4d3c3
Push 2 along s-d-b-t and draw the residual graph
s
2
t
Augmenting Path = Path in Gf
Let P be an s−t path in the residual graph Gf.
Let bottleneck(P) be the smallest capacity in Gf on any edge of P.
If bottleneck(P) > 0 then we can increase the flow by sending bottleneck(P) along the path P.
augment(f, P):
b = bottleneck(P)
for each e = (u,v) ∈ P:
if e is a forward edge:
decrease cf(e) by b //add some flow
else:
increase capacity by b //erase some flow
The Ford-Fulkerson Algorithm
Algorithm. Given (G, s, t, c)
start with f(u,v)=0 and Gf = G.
while exists an augmenting path in Gf
find bottleneck
augment the flow along this path
update the residual graph Gf
Example
a4b 286
10 c 9 d 10 Path s-a-c-d-t
10
s
10
t
Example
Path s-c-a-b-t
Path s-c-d-b-t
Example
Path s-c-d-a-b-t. Do it yourself.
Gf
In graph G edges are with flow/cap notation
G
10 a 1 b 3
s12716
9 c 9 d 10
1 9
t
a 3/4 b
9/10
0/2 7/8
9/10
10/10 s
t
c
9/9
6/6
d 10/10
The Ford-Fulkerson Algorithm Runtime Complexity
Algorithm. Given (G, s, t, 𝑐 ∈ N+) start with f(u,v)=0 and Gf = G.
while exists an augmenting path in Gf
find bottleneck
augment the flow along this path
update the residual graph
The worst-case
vct c1c
scu
c=109
O(|f| (E+V))
Proof of Correctness
How do we know the algorithm terminate
How do we know the flow is maximum?
t
a 3/4 b 9/10
10 a 1 b 1 39
Gf
s12716
9 c 9 d 10
G
s
10/10 9/10
0/2
7/8 9/9
6/6 d
t
10/10
c
Cuts and Cut Capacity
10 a 4 b 10 s28
t
96
10 c d 10
Cuts and Flows
Consider a graph with some flow and cut
8/10 a 0/4 b
A s 0/2 8/8 2/6
2/10 c 2/9 d 8/10
The flow-out of A is ___
The flow-in to A is ___
The flow across (A,B) is ___
What is a flow value |f| in this graph?
2/10
B
t
Lemma 1
For any flow f and any (A,B) cut
𝑓 = 𝑓(𝑠,𝑣ሻ = 𝑓(𝑢,𝑣ሻ− 𝑓(𝑣,𝑢ሻ 𝑣 𝑢∈𝐴,𝑣∈𝐵 𝑢∈𝐴,𝑣∈𝐵
Lemma 2
For any flow f and any (A,B) cut |f| ≤ cap(A,B).
Max-flow Theorem
Theorem. The Ford-Fulkerson algorithm outputs the maximum flow.
max 𝑓 = min𝑐𝑎𝑝(𝐴,𝐵ሻ 𝑓 𝐴,𝐵
a 3/4 b
9/10
s
9/10 Where is a min-cut ?
10/10
0/2
7/8 9/9
t
c
6/6
d 10/10
Discussion Problem 1
Run the Ford-Fulkerson algorithm on the following network:
16 B 12 C
19 49
T
S10 7
13 14 4
FE
How do you find a min-cut ? Is a min-cut unique?
Discussion Problem 2
You have successfully computed a maximum s-t flow for a network G = (V, E) with positive integer edge capacities. Your boss now gives you another network G’ that is identical to G except that the capacity of exactly one edge is decreased by one. You are also explicitly given the edge whose capacity was changed. Describe how you can compute a maximum flow for G’ in linear time.
12/16
S
11/13
B
12/12
C
19/19 0/4 0/9
4/4
T
0/10
7/7
11/14
FE
12/16
S
11/13
B
12/12
C
19/19 0/4 0/9
4/4
T
0/10
7/7
11/14
FE
Discussion Problem 3
If we add the same positive number to the capacity of every directed edge, then the minimum cut (but not its value) remains unchanged. If it is true, prove it, otherwise provide a counterexample.
Discussion Problem 4
In a daring burglary, someone attempted to steal all the candy bars from the CS department. Luckily, he was quickly detected, and now, the course staff and students will have to keep him from escaping from campus. In order to do so, they can be deployed to monitor strategic routes. Compute the minimum number of students/staff needed and show the monitored routes.
Reduction
Formally, to reduce a problem Y to a problem X (we write Y ≤p X) we want a function f that maps Y to X such that:
• f is a polynomial time computable
• ∀instance y ∈ Y is solvable if and only if f(y) ∈ X is solvable.
Solving by reduction to NF
1. Describe how to construct a flow network
2. Make a claim. Something like “this problem has a feasible solution if and only if the max flow is …”
3. Prove the above claim in both directions
X Y
people tasks
Bipartite Graph
A graph is bipartite if the vertices can be partitioned into two disjoint (also called independent) sets X and Y such that all edges go only between X and Y (no edges go from X to X or from Y to Y). Often writes G = (X, Y, E).
Bipartite Matching
Definition. A subset of edges is a matching if no two edges have a common vertex (mutually disjoint).
Definition. A maximum matching is a matching with the largest possible number of edges
Goal. Find a maximum matching in G.
Solving by Reduction
Given an instance of bipartite matching.
Create an instance of network flow.
The solution to the network flow problem can easily be used to find the solution to the bipartite matching.
Reducing Bipartite Matching to Network Flow
Given bipartite G = (X, Y, E). Let |X|=|Y|=V.
X
Y
Max matching = Max flow
S
1
X
1
Y
1
T
Max matching = Max flow
S
1
X
1
Y
1
T
Runtime Complexity Given bipartite G = (X, Y, E). , |X|=|Y|=V.
Discussion Problem 5
We’re asked to help the captain of the USC tennis team to arrange a series of matches against UCLA’s team. Both teams have n players; the tennis rating of the i-th member of USC’s team is ai and the tennis rating for the k-th member of UCLA’s team is bk. We would like to set up a competition in which each person plays one match against a player from the opposite school. Our goal is to make as many matches as possible in which the USC player has a higher tennis rating than his or her opponent. Give an algorithm to decide which matches to arrange to achieve this objective.
Player
Rating
Team
A
10
Trojans
B
5
Trojans
C
15
Trojans
D
20
Trojans
E
7
Bruins
F
14
Bruins
G
16
Bruins
H
19
Bruins
How to improve
the efficiency of the Ford-Fulkerson Algorithm?
O(|f| (E+V)) v c=109 t
c1c scu
Edmonds-Karp algorithm
Algorithm. Given (G, s, t, c)
1) Start with |f|=0, so f(e)=0
2) Find a shortest augmenting path in Gf
3) Augment flow along this path
4) Repeat until there is no an s-t path in Gf
Theorem.
The runtime complexity of the algorithm is O(V E2).
(without proof)
Runtime history
O(m U) O(n m2)
n = V, m = E, U = |f|
shortest path capacity scaling
preflow-push
splay tree preflow-push
2013 Orlin
O(m n)
Discussion Problem 6
A company has n locations in city A and plans to move some of them (or all) to another city B. The i-th location costs ai per year if it is in the city A and bi per year if it is in the city B. The company also needs to pay an extra cost, cij > 0, per year for traveling between locations i and j. We assume that cij = cji. Design an efficient algorithm to decide which company locations in city A should be moved to city B in order to minimize the total annual cost.
Discussion Problem 7
We say that two paths are vertex-disjoint if they do
not share any vertices (except s and t).
Given a directed graph G = (V, E) with two distinguished nodes s, t. Design an algorithm to find the maximum number of vertex-disjoint s-t paths in G.
Discussion Problem 8
There are n students in a class. We want to choose a subset of k students as a committee. There has to be m1 number of freshmen, m2 number of sophomores, m3 number of juniors, and m4 number of seniors in the committee. Each student is from one of k departments, where k = m1 +m2 +m3 +m4. Exactly one student from each department has to be chosen for the committee. We are given a list of students, their home departments, and their class (freshman, sophomore, junior, senior). Describe an efficient algorithm based on network flow techniques to select who should be on the committee such that the above constraints are all satisfied.