Assignment 3 CSE 565 Fall 2021 (Instructor: Mingfu Shao) Due: Oct 25, 11:59pm
INSTRUCTIONS:
1. Use the provided latex template to write your solutions.
2. Submit your solution to Gradescope: make sure only one of your group members submits. After
submitting, make sure to add your group members.
Problem 1 (15 points).
You are given a network G = (V,E) with positive integral capacity c(e) on e ∈ E, a source s ∈ V , and a
sink t ∈ V . Let f be an integral maximum s-t flow and G, and let G f be the residual graph w.r.t. f . Define
S1 = {v ∈V | s can reach v in G f } and T1 =V S1; T2 = {v ∈V | v can reach t in G f } and S2 =V T2.
1. Prove that (S2,T2) is one minimum s-t cut of G.
2. Let C be the set of all minimum s-t cut of G. Design a polynomial-time algorithm to compute the
intersection of s-side (i.e., S) of all minimum s-t cut (S,T ) in C , formally ∩C=(S,T )∈CS; design a
polynomial-time algorithm to compute the union of s-side (i.e., S) of all minimum s-t cut (S,T ) in
C , formally ∪C=(S,T )∈CS. Show the running time of your algorithm and prove that your algorithm is
correct. Hint: use Si and/or Ti, i= 1,2, in your algorithm.
3. Design a polynomial-time algorithm to decide if a given network has a unique minimum s-t cut. Show
the running time of your algorithm and prove that your algorithm is correct. Hint: use Si and/or Ti,
i= 1,2, in your algorithm.
Problem 2 (10 points).
You are given a directed graph G = (V,E) with unit integral capacity c(e) = 1 on e ∈ E, a source s ∈ V ,
and a sink t ∈ V . You are also given an integral maximum s-t flow f of G. Now we would like to pick k
edges from E and remove them from G such that the maximum flow of the new graph is reduced as much as
possible. In other words, find a set of edges F (F E, |F |= k) such that the max-flow of G′ = (V,E F) is
as small as possible. Design one polynomial-time algorithm to identify such k edges. You need to show run
time complexity analysis and correctness of your algorithm. A correct but high-complexity algorithm will
earn half of the total points of this problem.
Problem 3 (10 points).
You are given a network G= (V,E) with positive integral weight w(e) on e ∈ E, a source s ∈V , and a sink
t ∈ V . Now you need to find k different paths from s to v, and one edge can only be on one of the k paths.
The bottleneck of a path is defined as the largest weight of the edges on this path. Let L be the maximum
bottleneck among the k paths from s to t. Design an algorithm to find k paths so as to minimize L. Hint:
Read 7.6 [KT] and you may directly use any algorithm introduced there.
Problem 4 (10 points).
Given n booked taxi rides, each of the rides contains the source address, the destination address and the
departure time. We define an address as the street and avenue number (x,y). And it takes |x1 x2|+ |y1 y2|
time to drive from (x1,y1) to (x2,y2). A cab may carry out a booked ride if it is its first ride of the day, or
if it can get to the source address of the new ride from its latest, at least one minute before the new ride’s
scheduled departure. Design a polynomial-time algorithm, to find the minimum number of cabs required to
carry out all the booked taxi rides.
1
Assignment 3 CSE 565 Fall 2021 (Instructor: Mingfu Shao) Due: Oct 25, 11:59pm
Problem 5 (10 points).
Let’s call a floor plan, together with n light fixture locations and n switch locations, ergonomic if it’s possible
to wire one switch to one fixture (i.e., to pair them) so that every fixture is visible from the switch that
controls it. A floor plan will be represented by a set of m horizontal or vertical line segments in the plane
(the walls), where the i-th wall has endpoints (xi,yi),(x′i,y
′
i). Each of the n switches and each of the n fixtures
is given by its coordinates in the plane. A fixture is visible from a switch if the line segment joining them
does not cross any of the walls. Design an algorithm to decide if a given floor plan is ergonomic. The
running time should be polynomial in m and n. You may assume that you have a subroutine with O(1)
running time that takes two line segments as input and decides whether or not they cross in the plane, i.e.
whether a fixture is visible from a switch (visibility not blocked by a wall).
Figure 1: The floor plan in (a) is ergonomic, because we can wire switches to fixtures in such a way that
each fixture is visible from the switch that controls it. (This can be done by wiring switch 1 to a, switch 2 to
b, and switch 3 to c.) The floor plan in (b) is not ergonomic, because no such wiring is possible.
Problem 6 (10 points).
There are m mice and n holes on the ground of a warehouse; each is represented with a distinct 2D (x,y)
coordinates. A cat is coming and all mice are running to try to hide in a hole. Each hole can hide at most
k mice. All mice run at the same velocity v. A mouse is eventually safe if it reaches a hole (with at most k
mice including itself) in s seconds. Design a polynomial-time algorithm (in m and n) to find the maximum
number of mice that can be safe.
Problem 7 (10 points).
A company has n branches in one city, and it plans to move some of them to another city. The expenses for
operating the i-th branch is ai per year if it stays in the original city, and is bi per year if it is moved to the
new city. The company also needs to pay ci j per year for traveling if the i-th and j-th branches are not in the
same city. Design a polynomial time algorithm to decide which branches should be moved to the new city
such that the total expenses (including operating and traveling expenses) per year is minimized.
Problem 8 (5 points).
You are given an integer k, a set X and a collection C of subsets of X (e.g., each element of C is a subset
of X). Design a polynomial time (in terms of |X | and |C |) algorithm to decide whether there exists a subset
S C such that |S | ≥ k · |∪A∈S A|.
2
