CSCI 570 - Summer 2015 - HW 31. Solve Kleinberg and Tardos, Chapter 4, Exercise 8.Assume that T andˆT are two distinct minimum spanning trees for thethe graph. This implies that ∃e ∈ T such that e /∈ˆT . Adding e toˆTresults in a cycle C. Since the edge weights are distinct, there is a uniquemaximum weight edge emaxin C. By the cycle property (Prop. 4.20 intext) no minimum spanning tree can contain emax. This contradicts thefact that emaxis either in T or inˆT .NOTE : Problems 2 and 3 can be trivially solved by ignoring T andcomputing an MST for¯G from scratch. The objective of these exercises istherefore to come up with algorithms that run faster than computing fromscratch. For problem 3, you can assume that d is a constant independentof the number of vertices in G.2. Assume that you are given a graph G and a minimum spanning tree Tof G. A new edge e is added to G (without introducing any vertices) tocreate a new graph¯G. Design an algorithm that given G, T and e, findsa minimum spanning for¯G.We add the edge e to the minimum spanning tree T and this createsa (unique simple) cycle C. Let emaxbe an edge of maximum weight inthe cycle C. We claim that¯T := T ∪ {e} \ {emax} is a minimum spanningtree for the new graph¯G.Proof of claim:Since¯T is a tree and has |V | − 1 edges, it clearly spans¯G.If w(e) = w(emax), then by the cycle property (page 147, 4.20 in text) Tis an MST of¯G and since in this case¯T has the same weight at T ,¯T isan MST of¯G as well.We now deal with the case w(e) < w(emax). Since w(¯T ) = w(T) + w(e) −w(emax), we see that w(¯T ) < w(T ). Assume that¯T is not an MST of¯G.This implies that there exists¯Toptsuch that w(¯Topt) < w(¯T ).1Observe that it is necessary that e is contained in¯Topt, otherwise¯Toptwould be a spanning tree of G that is of weight lesser than the MST T .If we remove e from¯Topt, then we get two disjoint connected components(call them A and B). Since T is a spanning tree, there exists a uniqueedge e1in T that connects A and B. Further, by construction, e1is inthe cycle C. Construct the spanning tree T2:=¯Topt∪ {e1} \ {e} which isactually contained in G.w(¯Topt∪ {e1} \ {e}) = w(¯Topt) + w(e1) − w(e)< w(¯T + w(e1) − w(e)) = w(T ) + w(e) − w(emax) + w(e1) − w(e)= w(T) + w(e1) − w(emax)Since w(emax) ≤ w(e1), w(T2) < w(T ) and this contradicts the fact thatT is an MST of G. Hence our assumption is wrong and¯T is indeed anMST of¯G.Running Time: All we need to compute is the edge emax. Constructthe unique path (call P ) in T that connects the two ends of e. This canbe accomplished using BFS in O(n) time. The cycle C is P concatenatedwith e and we compute emaxas a maximum weighted edge in C.3. Assume that you are given a graph G = (V, E) and a minimum spanningtree T of G. A new edge v is added to G (along with d edges that connectv to G) to create a new graph¯G. Design an algorithm that given G, T ,vand the set of edges connecting v to G, finds a minimum spanning for¯G.Pick an edge f that crosses the cut (V, {u}). Clearly T ∪{f} is a minimumspanning tree of the graphˆG := (V ∪{u}, E ∪{f}). Observe that¯G can beobtained fromˆG by a sequence of edge additions. But from the solutionto problem 2, we know how to update the minimum spanning tree whenan edge is added ! Hence we have an algorithm to compute a minimumspanning tree for¯G by a sequence of updates. The degree of u is d and thecycle C that appears in each update step could be big (as big as O(|V |)).Thus the total running time is O(d|V |).Fun Problem: There is an algorithm that updates the MST in O(|V |log|V |)time even if d is as big as O(|V |). Can you think of such an algorithm ?4. You are given a weighted directed graph G = (V, E, w) and the shortestpath distances δ(s, u) from a source vertex s to every other vertex in G.However, you are not given π(u) (the predecessor pointers). With thisinformation, give an algorithm to find a shortest path from s to a givenvertex t in O(|V | + |E|) time.2Solution 1:(a) Starting from node t, go through the incoming edges to t one at atime to check if the condition δ(s, t) = w(u, t) + δ(s, u) is satisfied forsome (u, t) ∈ E.(b) There must be at least one node u satisfying the above condition,and this node u must be a predecessor of node t.(c) Repeat this check recursively, i.e. repeat the first step assuming nodeu was the destination instead of node t to get the predecessor to nodeu, until node s is reached.Complexity Analysis: Since each directed edge is checked at mostonce, the complexity is O(|V | + |E|). Note that constructing theadjacent list of Grevin order to facilitate access to the incomingedges is needed, which is still bounded by O(|V | + |E|) complexity.5. Given a directed graph with positive edge lengths and a source node sand a sink node t, design an algorithm to compute the number of shortestpaths from s to t.We modify Dijkstra’s algorithm (page 138) to accomplish this. For avertex u, let Count(u) denote the number of shortest paths from s to u.Initialize Count(s) = 1 and for all u 6= s, Count(u) = 0.When an edge (u, v) with u ∈ S, v /∈ S is relaxed, there are three cases toconsider for updating Count.If d(v) < d(u), do nothing.If d(v) > d(u) + `(u, v), then update Count[v] = Count[u] since we havefound a potential shortest path to v through u and u could be reached inCount[u] ways.If d(v) = d(u) + `(u, v), then set Count(v) = Count(v) + 1 since wehave found another way to get to v with the same length.6. Consider the following modification to Dijkstras algorithm for single sourceshortest paths to make it applicable to directed graphs with negative edgelengths. If the minimum edge length in the graph is w < 0, then addw + 1 to each edge length thereby making all the edge lengths positive.Now apply Dijkstras algorithm starting from the source s and output theshortest paths to every other vertex. Does this modification work? Eitherprove that it correctly finds the shortest path starting from s to every3vertex or give a counter example where it fails.Solution 1: No, the modification does not work. Consider the followingdirected graph with edge set {(a, b), (b, c), (a, c)} all of whose edge weightsare 1. The shortest path from a to c is {(a, b), (b, c)} with path cost 2. Inthis case, w = 1 and if w + 1 = 2 is added to every edge length beforerunning Dijkstras algorithm starting from a, then the algorithm wouldoutput (a, c) as the shortest path from a to c which is