EGRES Quick-Proof No. 2009-01 1On the Edge-Connectivity Algorithm of Nagamochiand IbarakiAndr´as Frank?AbstractThis note was written in 1994, while the author visited the J. Fourier Uni-versity of Grenoble, but it has never been published. The present facsimile ofthe original note serves its more convenient accessibility.?Egerv´ary Research Group of MTA-ELTE, Department of Operations Research, E¨otv¨os Univer-sity, P´azm´any P. s. 1/c. Budapest, Hungary, H-1117. e-mail: [email protected] 2009ON THE EDGE-CONNECTryITY ALGORITHMOF NAGAMOCHI AND IBARAKI(4. Frank)(March, 1994)'We are given an undirected (!) graph G : (V,^E) with n nodes and rn edges in whichparallel edges are allowed but loops not. Let c(x,U) : c(rrg;G) denote the minimumcardinality of a cut separating r and g. The edge-connectivity À(G) of G is the minimumof the c(r,A) values over all pairs of distinct nodes.It is well-known that À(G) may be computed by n - 1 applications of the MFMCalgorithm. H. Nagamochi and T. Ibaraki developed a revolutionary new algorithm tocompute À(G) that does not use flows, paths, Menger's theorem. This note presents theiralgorithm along with a simplified proof of its vaiidity.For two disjoint subsets X,Y of. nodes d(X,Y) denotes the number of edges connectingX and Y. We use d(X) :: d(X,V - X).For an ordering ?.r1r... ,t)n of the nodes o1. G,I{ denotes the set of the first i elements.We say that an ordering is legal ifd(V-t,ro) > d(V-t,ui)for every pair i,j (2 < i < j < n). (Viith the help of an appropriate data structure, aIegal ordering may be constructed in O(m) time.)One can easily observe that a legal ordering u1 ,t.. .t1),,, stays legal if we delete the edgesconnecting u' and l)n-t. Likewise, I)Lt. . . tlJn-t is legal for Gt :: G-un and u1 t. .. tun--2t,unis legal lor G't :: G - un-r. These facts will be used without any further reference.LEMMA c(un,un-1) : d(un,V*-t) (: d(u,")).Proof. Clearly, the left-hand side cannot be larger than the right-hand side. Hencewe need only to prove the ) direction. Assume, indirectly, that the lemma is not true andG is a minimal counter-example. Then, obviously, n ) 3.We claim that d(u,') : d(un,V^-z) or, equivalently, that there is no edge connectingu,. and 1)n-r. Indeed, by deleting such an edge we obtain a graph for which the lemmaholds but the lemma then would hold for G, as well.The lemma holds for G - u, and hence c(un-t,an_2) ) c(un_t,,un_2i" - ,_) >d(un-r,Vn-z) ) d(rn,Vn-z) : d(u-) where the last inequality follows from the legality ofthe given ordering.The lemma holds for the graph G - an_r and hence c(un,un_2) ) c(rn,un_2iG -0'.-1) ) d(an,V.-z): d(a-).Thus c(un.,u".-1) 2 min(c(un,un-z),c(un-r,u*-2)) 2. d(u.) contradicting the assumption that G is a counter-example. â(REMARK. The existence of two nodes x,y for which c(x,A) : d(x) was proved by W.Mader as early as 1972.)The aigorithm of Nagamochi and Ibaraki is based on the following observation. Letr and gr be two nodes for which d(r) : c(n,A). If there is a minimum cut of G (i.e. a cutof À(G) elements) separating r and g, then À(G) : d(r) and the star of e is such a cut.If no minimum cut of G separates r and g, then shrinking c and g into one node doesnot destroy any minimum cut. In this case it suffices to compute the edge-connectivity ofthe shrunken graph.These considerations along with the lemma verifies the correctness of the algorithm.Let Gr :: G and, iterate n - I times the following procedure. Assume that graph Grhas a,lready been constructed by successively shrinking i- 1 pairs of nodes (i : 2,. . . , n- 1).Determine a legal ordering of the nodes of. Gt and put in a list the last node sr of thisorder along with the value d(ro). (Here the subscript refers to the graph Gt.) Let G,a1 beconstructed from Gt by shrinking the last two nodes of the ordering.-When the n - 1 iterations is completed, choose an element xi of. the list for whichd("i) is minimum. À(G) is equal to d(x5). The node x5 of. Gi corresponds to a subsetXi of. nodes of the original G and hence d(Xi): À(G), that is, the cut IXi,V -X3] is aminimum cut of G.Since a legal ordering may be found in O(m) time, the complexity of the whole algo-rithm is
View Full Document
Unlocking...