Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP 465: Assignment
1. (20 pts) Consider the following network graph.
(a) (4 pts) Compute maximum flow f and minimum cut (S, T ).
(b) (3 pts) Draw the residual graph Gf - don’t forget to state the capacities. Indicate the minimum
cut (S, T ) in the residual graph by circling S and T .
(c) (4 pts) An edge is called constricting if increasing its capacity leads to an increase in the value
of maximum flow. List all constricting edges in the above network.
(d) (4 pts) Find a small (at most 4 nodes) example of a network graph that has no constricting
edges.
(e) (5 pts) Describe in plain English an efficient algorithm to find all constricting edges. Argue
correctness by using results from lectures/textbook. State the running time of your algorithm.
2. (20 pts) You are writing a computer game with the following puzzle. There is a room with n laser
pointers and n light receivers. Each laser pointer is fixed in its (x, y)-position but can be rotated 360
degrees to point the laser beam in any direction. Each light receiver is fixed in its (x, y)-position,
but it can receive laser beam from any direction. When a laser pointer points to a light receiver, the
light receiver is activated. A character enters a room and needs to rotate laser pointers to activate
all light receivers. See example below.
It turns out that not every placement of laser pointers and light receivers is such that all light receivers
can be activated. While writing this module of a game, you realise that it is helpful to have a function
that takes a description of a floor plan together with positions of n laser pointers and positions of n
light receivers and determines whether it is possible to activate all light receivers by rotating laser
pointers somehow. A floor plan is represented by a set of m horizontal or vertical line segments
(walls), where ith wall has endpoint coordinates (xi, yi), (x
′
i, y
′
i). A light receiver is activated by a
laser pointer if the line segment joining them does not cross the wall. Give an efficient algorithm for
Figure 1: An example of input (on the left) where laser pointers are represented by circles and light
receivers are represented by squares. The solution showing how laser pointers can be rotated to activate
light receivers is on the right.
this task. You may assume that you have a procedure that takes two line segments and determines
whether they intersect or not in O(1) time.
You may assume that no three objects (laser pointers or light receivers) are located on the same line.
Also, laser beams may freely pass through each other.
(a) (2 pts) State the problem formally using Input: . . ., Output: . . . format.
(b) (10 pts) Use flow networks to solve this problem. Give an English description of your algorithm.
Define flow network precisely. What is the set of vertices V ? What is the size of V ? What is the
set of edges E? What is the size of E? What is the source and the sink? What are capacities
on the edges? How do you get the answer to the original problem from this flow network?
(c) (5 pts) Argue why your algorithm is correct.
(d) (3 pts) State and justify the running time of your algorithm. It must be a function of m and n.
Figure 2: An example of input, where it is impossible to rotate laser pointers to activate all light receivers.
3. (20 pts) For each statement below state whether it is TRUE or FALSE (exclusive). For each answer
provide a brief justification or a small counter-example.
(a) (4 pts) If L1 ≤p L2 then L1 ≤p L2, where L = {0, 1}∗ − L denotes the complement.
(b) (4 pts) If P = NP then NP = co−NP .
(c) (4 pts) If L ∈ NP then L∗ ∈ NP .
(d) (4 pts) If L1 ≤p L2 and L2 ≤p L3 then L1 ≤p L3.
(e) (4 pts) If P = NP then LSPATH is NP-complete. LSPATH is the language corresponding to the
optimization problem: shortest s− t path.
4. (20 pts) Let G = (V,E) be a simple undirected graph. Recall that a set S ⊆ V is called a vertex cover
if every edge has at least one endpoint in S, i.e., ∀{u, v} ∈ E we have {u, v} ∩ S 6= ∅. The Minimum
Vertex Cover problem (MVC) asks to find a vertex cover of minimum size for a given graph G.
(a) (6 pts) State the optimization version, decision version, and search version of MVC.
(b) (14 pts) Let MVC−DEC denote the decision version of MVC. Recall that CLIQUE = {〈G, k〉 :
G has a clique of size at least k} is the decision version of the Maximum Clique problem. Show
that CLIQUE ≤p MVC −DEC. Give a reduction and prove its correctness and that it runs
in polynomial time.
5. (20 pts) Consider the following decision problem:
Input: two graphs G1 = (V1, E1) and G2 = (V2, E2), and an integer `.
Question: do there exist two sets of nodes W1 ⊆ V1 and W2 ⊆ V2 whose deletion leaves at least `
nodes in each graph and makes the resulting two graphs identical.
Prove that the above problem is NP-complete. You may assume NP-completeness results from
CLRS 34.5.