CSCI 570 – Summer 2021 – HW 4
due August 3, 2021
1 Graded Problems
1. The edge connectivity of an undirected graph is the minimum number of edges whose removal
disconnects the graph. Describe an algorithm to compute the edge connectivity of an undirected
graph with n vertices and m edges in O(m2n) time.
2. At a dinner party, there are n families a1, a2, …, an and m tables b1, b2, …, 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.
3. 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.
4. Solve Kleinberg and Tardos, Chapter 7, Exercise 7.
5. Solve Kleinberg and Tardos, Chapter 7, Exercise 9.
2 Practice Problems
1. 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.
1