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.