Discussion 8
1. You have successfully computed a maximum s-t flow f for a network G = (V; E) with integer edge
capacities. Your boss no gives ou another net ork G that is identical to G e cept that the capacit of
exactly one edge is decreased by one. You are also explicitly given the edge whose capacity was
changed. Describe ho ou can compute a ma imum flo for G in O( V + E ) time.
2. You need to transport iron-ore from the mine to the factory. We would like to determine how long it
takes to transport. For this problem, you are given a graph representing the road network of cities, with a
list of k of its vertices (t1, t2,…, tk) which are designated as factories, and one vertex S (the iron-ore mine)
where all the ore is present.
We are also given the following:
Road Capacities (amount of iron that can be transported per minute) for each road (edges)
between the cities (vertices).
Factory Capacities (amount of iron that can be received per minute) for each factory ( at t1, t2,…,
tk)
The amount of ore to be transported from the mine, C
Give a polynomial-time algorithm to determine the minimum amount of time necessary to transport and
receive all the iron-ore at factories.
3. 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.
More formally, we can think of the USC campus as a graph, in which the nodes are locations, and
edges are path a s or corridors. One of the nodes (the instructor s office) is the burglar s starting point,
and several nodes (the USC gates) are the escape points if the burglar reaches any one of those, the
candy bars will be gone forever. Students and staff can be placed to monitor the edges. As it is hard to
hide that many candy bars, the burglar cannot pass by a monitored edge undetected.
Give an algorithm to compute the minimum number of students/staff needed to ensure that the
burglar cannot reach an escape points undetected ( ou don t need to output the corresponding
assignment for students the number is enough). As input, the algorithm takes the graph G = (V,E)
representing the USC campus, the starting point s, and a set of escape points P ⊆ V . Prove that your
algorithm is correct and runs in polynomial time.
4. We define a most vital edge of a network as an edge whose deletion causes the largest decrease in
the maximum s-t-flow value. Let f be an arbitrary maximum s-t-flow. Either prove the following claims or
show through counterexamples that they are false:
(a) A most vital edge is an edge e with the maximum value of c(e).
(b) A most vital edge is an edge e with the maximum value of f (e).
(c) A most vital edge is an edge e with the maximum value of f (e) among edges belonging to
some minimum cut.
(d) An edge that does not belong to any minimum cut cannot be a most vital edge.
(e) A network can contain only one most vital edge.
Run Max Flor f
C is in Tons
f is in Tous Ihr
Min Time C in hrs
Cf
FEI
L I
I
ai
is t
Faohse
C Same as a
d Isham as a
e s It and same as b
Discussion 9
1. 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 (a positive number, where a
higher number can be interpreted to mean a better player) of the i-th member of USC’s team is ti
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. Use network flow to give an algorithm to decide which matches
to arrange to achieve this objective.
2. CSCI 570 is a large class with n TAs. Each week TAs must hold office hours in the TA office
room. There is a set of k hour-long time intervals I1, I2, … Ik in which the office room is available.
The room can accommodate up to 3 TAs at any time. Each TA provides a subset of the time
intervals he or she can hold office hours with the minimum requirement of lj hours per week, and
the maximum mj hours per week. Lastly, the total number of office hours held during the week
must be H. Design an algorithm to determine if there is a valid way to schedule the TA’s office
hours with respect to these constraints.
3. 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.
4. Given a directed graph G=(V,E) a source node s V, a sink node t V, and lower bound le for
flow on each edge e E, find a feasible s-t flow of minimum possible value.
Note: there are no capacity limits for flow on edges in G.
L C L
Say Max flow has valuevCfh
The restof the n k matches
can be randomly assigned
an alternate so I
s I o t
te
optimal Depts students danes optional
s.ee tds
g dt
E0analsoceseMaxFlows
Run Max Flor
check ref if Kfl kthus we have a Sol
mt.sk
d t04 o E dem
i e
o
c
d2 MZ
gd3 M3
I o
t o dyzmy
ct cap’s toe
C
construct G w edgecap’s
Ce fCe2 le
Rien Max flor mi o f
f fo fi
haidestprobbins
Easiestprob’s
1
p g
e g
haptotffon problems for
which we have
efficient
solutions
ornate
X cannotbe
solved in polyn fine
2
optimisation problem
Given a graph G and a no he
is there an independent set of
size at least K in G
Deasion version
112,3 4,5 6,2
qs 6 7 G
optimization versus
Given a graph G and a no heis then a vertex cover ofszeatmos.tk
Decision version
v die
case t Vis in S V is Not
VI will have U and not V
case 2 D is in S and V is Ntt
VI willhave V and not U
case 3 Neither now is in S
EE willhave both
Part B Suppose is a rentexfne.at
if G hasa vertex cover ofsize atmostn1
if G has an
eidep st of sjo at leastn k
i
iii iii
Before Lecture Notes – 12
Before Lecture Notes – 13