CSCI 570 – Summer 2020 – HW 5
Due August 5th
1 Graded Problems
1. State True/False: For any flow network G and any maximum flow on G,
there is always an edge e such that increasing the capacity of e increases
the maximum flow of the network. Justify your answer.
2. Suppose that you are given a flow network G, and G has edges entering
the source s. Let f be a flow in G in which one of the edges (v, s) entering
the source has f(v, s)=1. Prove that there must exist another flow f ′
with f ′(v, s) = 1 such that |f | = |f ′|. Give an O(|E|)-time algorithm to
compute f ′, given f, and assuming that all edge capacities are integers.
3. Suppose that you wish to find, among all minimum cuts in a flow network
G with integral capacities, one that contains the smallest number of edges.
Show how to modify the capacities of G to create a new flow network G′ in
which any minimum cut in G′ is a minimum cut with the smallest number
of edges in G.
4. Solve Kleinberg and Tardos, Chapter 7, Exercise 7.
5. At a dinner party, there are n families a1, …, an and m tables b1, …, bm.
The i− th family ai has gi members and the j − th table bj has hj seats.
Everyone is interested in making new friends and the dinner party planner
wants to seat people such that no two members of the same family are
seated in the same table. Design an algorithm that decides if there exists
a seating assignment such that everyone is seated and no two members of
the same family are seated at the same table.
6. There is a precious diamond that is on display in a museum at m disjoint
time intervals. There are n security guards who can be deployed to protect
the precious diamond. Each guard has a list of intervals for which he/she
is available to be deployed. Each guard can be deployed to at most A time
slots and has to be deployed to at least B time slots. Design an algorithm
that decides if there is a deployment of guards to intervals such that each
interval has either exactly one or exactly two guards deployed.
1
7. An edge of a flow network G is called critical if decreasing the capacity
of this edge results in a decrease in the maximum flow. Is it true that
with respect to a maximum flow of G, any edge whose flow is equal to its
capacity is a critical edge? Give an efficient algorithm that finds a critical
edge in a flow network.
2 Practice Problems
1. Solve Kleinberg and Tardos, Chapter 7, Exercise 6.
2. Solve Kleinberg and Tardos, Chapter 7, Exercise 11.
3. Solve Kleinberg and Tardos, Chapter 7, Exercise 13.
4. Solve Kleinberg and Tardos, Chapter 7, Exercise 28.
5. Solve Kleinberg and Tardos, Chapter 7, Exercise 34.
2