Minimum spanning tree in sparse graphs For a very sparse

Chapter 23, Problem 23-2

(choose chapter or problem)

Minimum spanning tree in sparse graphs For a very sparse connected graph G D .V; E/, we can further improve upon the O.E C V lg V / running time of Prims algorithm with Fibonacci heaps by preprocessing G to decrease the number of vertices before running Prims algorithm. In particular, we choose, for each vertex u, the minimum-weight edge .u; / incident on u, and we put .u; / into the minimum spanning tree under construction. We then contract all chosen edges (see Section B.4). Rather than contracting these edges one at a time, we first identify sets of vertices that are united into the same new vertex. Then we create the graph that would have resulted from contracting these edges one at a time, but we do so by renaming edges according to the sets into which their endpoints were placed. Several edges from the original graph may be renamed the same as each other. In such a case, only one edge results, and its weight is the minimum of the weights of the corresponding original edges. Initially, we set the minimum spanning tree T being constructed to be empty, and for each edge .u; / 2 E, we initialize the attributes .u; /:orig D .u; / and .u; /:c D w.u; /. We use the orig attribute to reference the edge from the initial graph that is associated with an edge in the contracted graph. The c attribute holds the weight of an edge, and as edges are contracted, we update it according to the above scheme for choosing edge weights. The procedure MST-REDUCE takes inputs G and T , and it returns a contracted graph G0 with updated attributes orig0 and c0 . The procedure also accumulates edges of G into the minimum spanning tree T . MST-REDUCE.G; T / 1 for each 2 G:V 2 :mark D FALSE 3 MAKE-SET./ 4 for each u 2 G:V 5 if u:mark == FALSE 6 choose 2 G:Adju such that .u; /:c is minimized 7 UNION.u; / 8 T D T [ f.u; /:origg 9 u:mark D :mark D TRUE 10 G0 :V D fFIND-SET./ W 2 G:Vg 11 G0 :E D ; 12 for each .x; y/ 2 G:E 13 u D FIND-SET.x/ 14 D FIND-SET.y/ 15 if .u; / 62 G0 :E 16 G0 :E D G0 :E [ f.u; /g 17 .u; /:orig0 D .x; y/:orig 18 .u; /:c0 D .x; y/:c 19 else if .x; y/:c < .u; /:c0 20 .u; /:orig0 D .x; y/:orig 21 .u; /:c0 D .x; y/:c 22 construct adjacency lists G0 :Adj for G0 23 return G0 and T a. Let T be the set of edges returned by MST-REDUCE, and let A be the minimum spanning tree of the graph G0 formed by the call MST-PRIM.G0 ; c0 ;r/, where c0 is the weight attribute on the edges of G0 :E and r is any vertex in G0 :V. Prove that T [ f.x; y/:orig0 W .x; y/ 2 Ag is a minimum spanning tree of G. b. Argue that jG0 :Vj jV j =2. c. Show how to implement MST-REDUCE so that it runs in O.E/ time. (Hint: Use simple data structures.) d. Suppose that we run k phases of MST-REDUCE, using the output G0 produced by one phase as the input G to the next phase and accumulating edges in T . Argue that the overall running time of the k phases is O.kE/. e. Suppose that after running k phases of MST-REDUCE, as in part (d), we run Prims algorithm by calling MST-PRIM.G0 ; c0 ;r/, where G0 , with weight attribute c0 , is returned by the last phase and r is any vertex in G0 :V. Show how to pick k so that the overall running time is O.E lg lg V /. Argue that your choice of k minimizes the overall asymptotic running time. f. For what values of jEj (in terms of jV j) does Prims algorithm with preprocessing asymptotically beat Prims algorithm without preprocessing?