Cos 423 Problem Set 3 Due Monday April 2, 2007Spring 2007 Collaboration Allowed1. (Minimum-exposure scanning) Consider the following version of the labeling andscanning algorithm, which we shall call minimum-exposure scanning. Each vertex v hasa score ( ),r vwhich is initialized to be its in-degree. The rule for selecting a vertex todelete from L and scan is to always pick one of minimum score. In addition, when anedge ( , )v wis examined while scanning,vwhether or not ( ) ( ) ( , ), ( )d w d v c v w r w> + isreduced by one unless it is already zero, in which case it is not changed.(a) Describe how to implement minimum-exposure scanning so that the total overheadfor choosing vertices to scan is O( )n m+plus O(1)per scan.(b) Suppose that the graph contains no cycles and that all vertices are reachable from .sProve that minimum-exposure scanning will scan each vertex exactly once, and thatwhen v is scanned ( ) 0.r v = Thus show that in this case the running time of the algorithmis O( ),m and the implementation can be simplified from (a) to merely maintain the set oflabeled vertices with zero value.r -2. (Bitonic shortest paths: see problem 24-6, page 618 of the text). Given a graph withedge lengths, a path from s to t is bitonic if there is a vertex v on the path (possibly sor )tsuch that that the lengths of the edges along the part of the path from s to v arenon-decreasing, and the lengths of the edges along the part of the path from v to t arenon-increasing.The single-source shortest bitonic path problem is that of finding a shortest bitonic pathfrom s to every vertex. Give the most-efficient algorithm that you can for solving thesingle-source shortest bitonic path problem on an arbitrary graph. As output, it suffices toreport the lengths of shortest bitonic paths to each vertex, not the paths themselves.3. (Minimum spanning trees in large-girth graphs) We call a graph large-girth if itcontains no cycle with fewer than lg nedges. Describe and analyze a deterministicalgorithm that will compute a minimum spanning tree of a large-girth graph in O( )mtime. (You can assume that the graph is connected.)Extra credit: solve the same problem, but define a graph to be large-girth if it contains nocycle with less than lg n* edges.4. (Equitable flows) Consider a flow network such that there is no arc from s to ,t andall arcs out of s have infinite capacity. Such a network (or indeed any network) can havemany maximum flows. In order to choose among such alternatives, we define anequitable flow as follows: the equitable flow is the maximum flow that maximizes theminimum of the flows on arcs out of,sbreaking a tie by maximizing the second-minimum of the flows on arcs out of ,s and so on. More precisely, let 1, 2, 3...f f fbethe flows on arcs out of ,s in non-decreasing sorted order. The flow is equitable if thisvector is largest possible in lexicographic order. (One vector is lexicographically biggerthan another if, for some ,i their first i components are equal but the first vector has abigger 1sti +component.) (a) Prove that a flow f is equitable if and only if it is a maximum flow and, for every pair of vertices x and y such that ( , ) ( , ),f s x f s y< there is no augmenting path from x to .y (b) Give the most efficient algorithm you can to find an equitable