COS 423 Problem Set No. 4Spring 2007 Due Monday April 161. (Nested Cycles Decomposition) Given a strongly connected directed graph, a nestedcycles decomposition of the graph is constructed as follows: Find any cycle in the graph.Contract the cycle into a single vertex, and eliminate loops (edges of the form ( , ))v vandmultiple edges. Repeat until only a single vertex remains. As the contraction processproceeds, each vertex of the contracted graph is either an original vertex or correspondsto a non-trivial strongly connected subgraph of the original graph. We can represent anested cycles decomposition by a rooted, ordered decomposition tree, whose leaves arethe original vertices and whose internal nodes are the vertices formed by contraction,with the children of each vertex those on the cycle contracted to form it, ordered in thesame order they occur along the cycle. (This order is only unique up to a cyclic shift; thatis, any vertex can be the first child, then the order of the rest is uniquely determined).Give the fastest algorithm you can to find a nested cycles decomposition of an arbitrarystrongly connected digraph. Your algorithm should build a corresponding decompositiontree. Determine the asymptotic running time of your algorithm.2. (Greedy Matching) Consider the following greedy method for finding a matching inan arbitrary undirected graph (not necessarily bipartite). Choose any edge, add it to thematching, and delete all edges that share an end with the selected edge. Repeat untilthere are no more edges.(a) Give an O( ) timen m+ -implementation of this algorithm.(b) Prove that the algorithm always finds a matching within a factor of two of maximum(in number of edges), and show by means of an example that this factor of two is bestpossible.(c) (extra credit) Consider the weighted version of this algorithm: given an undirectedgraph with non-negative edge weights, run the algorithm above, always choosing amaximum-weight remaining edge. What is the best running time you can obtain for thisgeneralization of the algorithm? What can you say, if anything, about how close it comesto finding a matching of maximum total weight?3. (Road Connections) Consider a directed graph representing a partially constructedroad network (of one-way streets). Your goal is to find a set of additional arcs, minimumin number, to add to the graph to make it strongly connected. Give the fastest algorithmyou can to solve this problem. State and prove the asymptotic running time of youralgorithm. Can you give a formula for the number of edges needed in terms of someparameters of the original graph?4. (Live Vertex Preflow Push Algorithm) Consider the following modification of thepreflow push algorithm. A vertex v is live if, for every distance k such that( ) 0,d v k> > there is at least one vertex w with ( ) .d w k= (Here ( )d uis the distancelabel of vertex .)u The live vertex preflow push algorithm is the variant of the preflowpush algorithm that discharges an active live vertex of highest distance label, stopping thedischarge of such a vertex as soon as it becomes dead (because of an increase in itsdistance label) and setting its distance label equal to n.(a) Prove (i) every live vertex has label less than n, and thus (ii) there are no pushes from live to dead vertices and (iii) no dead vertex ever becomes live. (b) Prove that when the algorithm stops, the cut whose source side is the set of deadvertices is a minimum cut. (c) When the algorithm stops, there may still be (dead) vertices that are active. Give anexample. Describe the fastest algorithm you can that will convert the final preflow into amaximum flow (by routing the remaining excess back to the source). (An O( ) timenm -solution will suffice. The fastest solution I know is O( log ) time,m n - but it uses a datastructure we have not discussed in class.) (d) Describe a way to implement the algorithm so that the overhead to keep track of thelive and dead vertices, and to select vertices to discharge, is O(1) per relabeling (by one)of a vertex.(e) Prove that the algorithm runs in 3O( )ntime.(f) (extra credit) Is the 3O( )n bound tight, or can you obtain a better