Analysis of Algorithms
V. Adamchik CSCI 570 Spring 2020 Lecture 9 University of Southern California
Network Flow
Reading: chapter 7
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
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
Path s-c-d-a-b-t
Example
10 a 1 b 3
s12716
9 c 9 d 10
Gf
1 9
t
In graph G edges are with flow/cap notation
G
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, 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
The worst-case
vct c1c
scu
c=109
O(|f| (E+V))
Proof of Correctness
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 𝑓 ≤ min𝑐𝑎𝑝(𝐴,𝐵ሻ 𝑓 𝐴,𝐵
Max-flow Theorem
Theorem. The Ford-Fulkerson algorithm outputs
the maximum flow.
10/10
s
9/10
a 3/4 b
9/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
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.
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
Professor Jones has determined that x priceless artifacts are located in a labyrinth. The labyrinth can be thought of as a graph, with each edge representing a path and each node an intersection of paths. All of the artifacts are in the same treasure room, which is located at one of the intersections. However, the artifacts are extremely burdensome, so Jones can only carry one artifact at a time. There is only one entrance to the labyrinth, which is also a node in the graph. The entrance serves as the only exit as well. All the paths are protected by human-eating vines, which will be woken up after someone passes the path, so Jones can only go through each path once. Give an algorithm that determines how many artifacts Jones can obtain and how he can do it.
4 25
1 s
t 6
3
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.