Homework 5 Solutions COMS 311
1. Let G = (V,E) be a directed graph. Given a vertex v let from(v) denote the set of vertices that have a path from v (excluding v), and let to(v) be the set of vertices from which there is a path to v. A vertex v is (1/4, 3/4)-bridge, if the size of f rom(v) is (n − 1)/4, the size of to(v) is 3(n − 1)/4,and from(v) ∩ to(v) = ∅. Given a graph (where n − 1 is divisible by 4), give an algorithm that outputs all (1/4, 3/4)-bridge vertices. If the graph does not have such bridge vertices, then the algorithm returns null. Prove the correctness and derive the runtime.
Ans. We know the following property of DFS: If there is a path from u to v and there is no path from v to u, then EndTime(u) > EndTime(v). Suppose that the graph has a Bridge Vertex v. Note that there is a path from v to every vertex in from(v), however there is no path from any vertex in from(v) to v (otherwise from(u) is not disjoint from to(v)). Similarly there is a path from every vertex in to(v) to v and there is no path from v to any vertex in to(v). Thus EndTime of v must be larger than the end time of every vertex from from(v) and smaller than the endtime of every vertex in to(v). This implies that EndT ime(v) = 3(n − 1)/4 + 1. This suggests the following algorithm:
1. Perform DFS and let v be a vertex whose end time is 3(n − 1)/4 + 1. 2. Compute f rom(v) by doing BFS from v and check that the size of from(v) is 3(n − 1)/4. 3. Do a BFS in the reverse graph from v to compute to(v), and check that the size of to(v) is (n − 1)4/. 4. Finally check that f rom(v) is disjoint from to(v). Since V = {1, · · · , n} this can be done by using a bit array B of size n. For every i ∈ from(v) set B[i] = 1. Now for every j ∈ to(v), check B[j] = 1. If B[j] equals 1 for some j ∈ To(v) then the sets are not disjoint, else they are disjoint. 4. Output v if it passes all the tests.
Time taken by the first three steps is O(m + n) and the time taken by the last step is O(n). Thus the total time is O(m + n). Finally, note that there can be only one bridge vertex.
2. Let G = (V, E) be a directed, weighted graph with positive edge weights and let s ∈ V . Recall that any tree Π rooted at s can be represented by a parent array as follows: Π(s) = null and Π(x) = parent of x in the tree.
• Suppose that Π is a shortest path tree of G rooted at s. Give an algorithm, that gets G and Π as input, and computes the length of the shortest path from s to every vertex. Derive the runtime.
Ans. Create a Distance array d and set d[s] = 0. Perform BFS on the Π starting at node s. When the BFS discovers an edge ⟨u, v⟩, then set d[v] = d[u] + c(⟨u, v⟨).
Time taken is O(m + n).
1
• You are given a candidate shortest path tree Π. Given an algorithms that gets G and Π as input, and checks if Π is indeed a shortest path tree. Justify the correctness and derive runtime.
Ans. Using the above algorithm, computes a candidate distance array d. Now check the following:
– d[s] = 0.
– For every v check that
∗ d[v] = minu{d(u) + c(⟨u, v⟩| ⟨u, v⟩ ∈ E}
• If all the checks succeed then output true else output false.
Note that if a shortest path from s to v, goes to u and then takes the edge ⟨u, v⟩, then it must be the case that the path from s to u must be the shortest path. The correctness follows from this observation.
Time taken is O(m + n).
3. Let G = (V,E) be an undirected, connected and weighted graph and let T be its Minimum Spanning Tree. Let G′ be a graph obtained by decreasing weight of an edge e ∈ E by a positive quantity x. Give an algorithm that gets G,T , e and x and computes a MST of G′. Your algorithm must run in O(m + n) time. Prove correctness of your algorithm and state its runtime.
Ans. Ife∈T,thenT istheMSTofG′. Ife∈/T,thenadde=⟨x,y⟩toT,thisinducesa cycle in T. Compute this cycle by finding a path from x to y. Now remove the largest weight edge from this cycle, this results in a new tree T′. This is the new MST. The correctness follows from the cycle property. Runtime is O(m + n) as finding a path in T takes O(n) time and finding the weights of edges in T takes O(m + n) time.
4. Consider a simplistic pipeline of a car manufacturing plant consisting of two phases. In the first phase, a robot assembles all the parts of a car. The second phase paints the assembled car. There is only one robot and thus only one car can be assembled at a time. However, the plant has enough employees (and supplies) who can paint the car. Thus multiple cars can be painted at the same time (in parallel). Different types of cars take different amounts of time to be assembled (by the robot) and painted (by the employees). Suppose that car Ci requires ai minutes of assembling time, plus pi minutes of painting time. The goal is to write an algorithm that, given a set of n cars C1, C2, · · · Cn along with their assembling and painting times, determines a schedule Ci1 , Ci2 , . . . , Cin such that all the cars are completely finished (assembled and painted) in the shortest overall time.
• Consider the schedule obtained by sorting the assembly times in decreasing order. Show that this algorithm does not produce optimal answer.
• Consider the schedule obtained by sorting the paint times in decreasing order. Prove that this algorithm produces optimal solution. Use exchange argument to prove the correctness.
Ans. We will use an exchange argument to prove the correctness of the algorithm. We know that all paint times are distinct.
2
Let c1,c2,···cn be an optimal schedule O with assemble and paint times being ai and pi for ci. We say that this schedule has an inversion if i < j but pi < pj. Note that schedule produced by the greedy algorithm as no inversions. In this schedule, let g(l) be the time at which car cl is completely finished, and let f(l) be the time at which car cl is done with assembling and painting. Note that f(l) = g(l) + pl. Also note that g(l) = g(l−1)+al. Let S = max{f(1),f(2),···f(k)}. Thus all cars are finished within S time units. Since O is an optimal schedule we can not have another schedule in which all cars are finished in less than S time units.
Observation: If an optimal schedule has an inversion, then there exist k such that pk < pk+1. Proof: Since optimal schedule has an inversion, there exist i < j such that pi < pj. Consider pi,pi+1,pi+2,···pj. Since pi < pj it can be the case that pi > pi+1 > pi+2 ···pj. Thus there is a k between i and j such that pk < pk+1. Consider a schedule O′ which is same as O except that ck and ck+1 are swapped. In this schedule, let g′(l) be the time at which car cl is done assembling, and let f′(l) be the time at which car cl is done with assembling and painting. Let S′ = max{f′(1), f′(2), · · · f′(k)}.
Since O is an optimal schedule S′ ≥ S.
Note that g′(1) = g(1), g′(2) = g(2), · · · g′(k−1) = g(k−1) and g′(k+2) = g(k+2), g′(k+
3) = g(k+3)···g′(n) = g(n) and thus f′(1) = f(1),f′(2) = f(2),···f′(k−1) = f(k−1) and f ′ (k + 2) = f (k + 2), f ′ (k + 3) = f (k + 3) · · · f ′ (n) = f (n).
How do f(k),f(k+1),f′(k) and f′(k+1) compare? Note that in the new schedule ck+1 is assembled after ck−1 and in the old schedule ck+1 is assembled after ck−1 and ck are done. Thusg′(k+1)