Review NetworkFlow
Network Flow
Practice Problem #1 – People and Sets
• There are n people, p1, p2, …, pn and k sets.
• Each set consists of several people and a person can be in more than
one set.
• We need to select one person from each set and the maximum times
a person is selected should be less than m.
• Give a polynomial time algorithm to find such a selection if there is
one, or to indicate that such a selection is not possible. Prove that
your solution is correct.
Practice Problem #1 – People and Sets
• Construct a graph with n vertices p1, p2, …, pn corresponding to the n people, k
vertices s1, s2, …, sk corresponding to the k sets, and two special vertices s and t.
• For i = 1, …, n, put an edge from s to pi with capacity m – 1.
• Put an edge from pi to sj with capacity 1 if person pi is in the sj.
• For j = 1, …, k, put an edge from sj to t with capacity 1.
p1
p2
s1
p3
p4
s2
s
t
2
2
2
2
1
1
1
1
1
1
1
Example:
4 people (n=4)
2 sets (k=2)
m = 3
people
set
Practice Problem #1 – People and Sets
• We now find a maximum flow in this graph. If the flow has value k (the number of
sets), then there is a way to select one person from each set such that each
person is not selected more than m – 1 times.
• The flow has one incoming edge for each set; if for set sj this edge comes from
person pi then pi is the person selected for set sj.
p1
p2
s1
p3
p4
s2
s
t
2
2
2
2
1
1
1
1
1
1
1
Example:
4 people (n=4)
2 sets (k=2)
m = 3
Practice Problem #1 – People and Sets
• To prove that the solution is correct is to prove that the reduction is correct: the
graph has a maximum flow of value k only if there is a way to select one person
from each set such that each person is not selected more than m – 1 times.
• Since the graph has a flow of value k, those edges from sj to t are all saturated.
The conservation constraint for each sj implies that some person in sj is selected.
The capacities of those edges from s to pi being m – 1 ensure that each person is
selected less than m times.
p1
p2
s1
pn
sj
s
t
m – 1
m – 1
m – 1
1
1
1
1
1
1
1
k sets
…
…
Practice Problem #2 – Client-Base
• Consider a set of mobile computing clients in a certain town who each need to be
connected to one of several possible base stations. We’ll suppose there are n clients,
with the position of each client specified by its (x, y) coordinates in the plane. There are
also k base stations; the position of each of these is specified by (x, y) coordinates as
well.
• For each client, we wish to connect it to exactly one of the base stations. Our choice of
connections is constrained in the following ways:
• There is a range parameter r— a client can only be connected to a base station that is within distance r.
• There is also a load parameter L— no more than L clients can be connected to any single base station.
• Your goal is to design a polynomial-time algorithm for the following problem. Given the
positions of a set of clients and a set of base stations, as well as the range and load
parameters, decide whether every client can be connected simultaneously to a base
station, subject to the range and load conditions in the previous paragraph.
Practice Problem #2 – Client-Base
• We build the following flow network:
• There is a node vi for each client i, a node wj for each base station j.
• There is an edge (vi, wj) of capacity 1 if client i is within range of base station j.
• We then connect each of the base station nodes to a super-sink t by an edge
of capacity L.
V1
V1
w1
V1
V1
w2
s
t
1
1
1
1
1
1
1
1
1
1
L
L
clients
stations
Practice Problem #2 – Client-Base
• We claim that there is a feasible way to connect all clients to base stations if and
only if there is an s-t flow of value n (number of clients).
• If there is a feasible connection, then we send one unit of flow from s to t along each of the
paths s, vi, wj, t, where client i is connected to base station j.
• This does not violate the capacity conditions, in particular on the edges (wj, t), due to the
load constraints.
V1
V1
w1
V1
V1
w2
s
t
1
1
1
1
1
1
1
1
1
L
L
clients
stations
Practice Problem #2 – Client-Base
• Conversely, if there is a flow of value n, then there is one with integer values.
• We connect client i to base station j if the edge (vi, wj) carries one unit of flow, and we
observe that the capacity conditions ensures that no base station is overloaded.
• The running is the time required to solve a max-flow on a graph with O(n+k)
nodes and O(nk) edges.
V1
V1
w1
V1
V1
w2
s
t
1
1
1
1
1
1
1
1
1
L
L
clients
stations
Practice Problem #3 – Conference Papers
Suppose you are organizing a conference where researchers present articles they have written:
• Researchers who want to present an article send a paper to the conference organizers.
• The conference organizers have access to a committee of reviewers who are each willing to read
up to mB articles each.
• Each paper submission gets reviewed by up to mA reviewers.
• Moreover, each submission has a particular topic and each reviewer has a specialization for a set
of topics, so papers on a given topic only get reviewed by those reviewers who are experts on that
topic.
• The conference organizers need to decide which reviewers will review each article (or
equivalently, which articles will be reviewed by which reviewers).
Explain how they could use a flow network to solve this problem.
Practice Problem #3 – Conference Papers
• There is a set A of articles and a set B of reviewers. (We could define it the other
way around.)
• Add a directed edge (α, β) to the graph if some article α in A could be reviewed by
some reviewer β in B, namely the article is on a topic that the reviewer is an
expert in. Set the capacity of that edge to be 1.
α1
α2
β1
α3
α4
β2
1
1
1
1
1
articles
reviewers
Practice Problem #3 – Conference Papers
• Add a vertex s (source) and a vertex t (terminal).
• For each α in A, add an edge (s, α) of capacity mA (max number of reviewers).
• For each β in B, add an edge (β , t) of capacity mB (max number of articles to review).
• Run Ford-Fulkerson to get the maximum flow and compute the corresponding cut(A,B).
This gives the set of edges which correspond to the assignment of articles to reviewers.
α1
α2
β1
α3
α4
β2
s
t
mA
mA
mA
mA
1
1
1
1
1
mB
mB
Practice Problem #4 – Blood Bank
• A hospital has 155 bags of blood in stock and 150 patients that need to get a
transfusion of one bag. The distribution of blood groups in the supply and
amongst the patients is shown in the table below.
• Type A patients can only receive blood of type A or type O; type B patients can receive
only type B or type O; type O patients can receive only type O; and type AB patients can
receive any of the four types.
• Describe how to check whether every student can get a transfusion, otherwise how
many can get one.
Blood Type A B O AB
Bags in stock 44 31 42 38
Demand 37 33 40 40
Practice Problem #4 – Blood Bank
• Create a graph G with a source node s, a sink node t, 4 nodes for the supply of
each blood type sT (where T is the blood type), and 4 nodes for the demand of
each blood type dT.
• Make an edge from sT to dU with unlimited capacity iff a patient with blood type
T can use blood of type U.
sA
sB
sO
sAB
dA
dB
dO
dAB
bags patients
∞
∞
∞
∞
∞
∞
∞
∞
Practice Problem #4 – Blood Bank
• Make an edge from s to sT with capacity equal to the number of bags in stock of
blood type T.
• Make edges from dT to t with capacity equal to the number of students with
blood type T
sA
sB
sO
sAB
dA
dB
dO
dAB
bags patients
s
Blood Type A B O AB
Bags in stock 44 31 42 38
Demand 37 33 40 40
40
31
42
38
t
37
33
44
40
∞
∞
∞
∞
∞
∞
∞
∞
Practice Problem #4 – Blood Bank
• Use a maximum flow algorithm like Ford-Fulkerson to find the maximum s − t
flow in G. If the value of the maximum flow equals the number of students then
all students can get a transfusion, otherwise the maximum flow is the number of
students that can.
sA
sB
sO
sAB
dA
dB
dO
dAB
bags patients
s
Blood Type A B O AB
Bags in stock 44 31 42 38
Demand 37 33 40 40
40
31
42
38
t
37
33
44
40
∞
∞
∞
∞
∞
∞
∞
∞
Practice Problem #5 – Feasible Circulation
In the network below, the demand values are shown on vertices
(supply value, if negative). Lower bounds on flow and edge capacities
are shown as (lower bound, capacity) for each edge. Determine if there
is a feasible circulation in this graph.
Lower bound
Capacity
Supply
Demand
Practice Problem #5 – Feasible Circulation
A feasible circulation doesn’t exist. In the given network, total demand
values on the vertices doesn’t match with the total supply value on all
the vertices.
Lower bound
Capacity
Supply
Demand
Practice Problem #5 – Feasible Circulation
Let’s balance the demand on the network.
-13
Practice Problem #5 – Feasible Circulation
Turn the circulation with lower bounds problem into a circulation problem without
lower bounds:
• Capacity of edge -> ce – le
• Demand of node -> dv – Lv
• Lv = ∑” #$%& ‘ 𝑙” − ∑” &*% &+ ‘ 𝑙”
-13
-8
Practice Problem #5 – Feasible Circulation
Turn the circulation with demands problem into the maximum flow problem:
• Attach a super-source s to each node in S with capacity – dv
• Attach a super-sink t to each node in T with capacity dv
-8
8
4
5
7
Practice Problem #5 – Feasible Circulation
• v(f) < D • A feasible circulation doesn’t exist • v(f) should be equal to D to exist a feasible circulation 8 4 5 7