Poly-Logarithmic Deterministic Fully-Dynamic Algorithmsfor Connectivity, Minimum Spanning Tree, 2-Edge,and BiconnectivityJACOB HOLM AND KRISTIAN DE LICHTENBERGUniversity of CopenhagenANDMIKKEL THORUPAT&T Labs—Research, Florham Park, New JerseyAbstract. Deterministic fully dynamic graph algorithms are presented for connectivity, minimumspanning tree, 2-edge connectivity, and biconnectivity. Assuming that we start with no edges in agraph with n vertices, the amortized operation costs are O(log2n) for connectivity, O(log4n) forminimum spanning forest, 2-edge connectivity, and O(log5n) biconnectivity.Categories and Subject Descriptors: E.1 [Data Structures]: Graphs and Networks; F.2.2 [Theory ofComputation]: Nonnumerical Algorithms and Problems—computation on discrete structures; G.2.2[Mathematics of Computing]: Discrete Mathematics—graph algorithmsGeneral Terms: AlgorithmsAdditionalKeyWordsandPhrases:Biconnectivity,connectivity,dynamicgraphalgorithms,minimumspanning tree, 2-edge connectivity1. IntroductionWe consider the fully dynamic graph problems of connectivity, minimum spanningforest, 2-edge connectivity and biconnectivity. Here, by fully dynamic, we meanthat the graph may be updated by insertion and deletion of edges. If we only allowinsertions or only allow deletions, the graph is only partially dynamic. The updatesare interspersed with queries to the current graph. The update and query operationsare presented on-line, with no knowledge of future operations.A preliminary version of this work was presented at the 30th ACM Symposium on the Theory ofComputing (STOC’98) [Holm et al. 1998]. The conference version mistakenly claimed an O(log4n)instead of an O(log5n) for biconnectivity.The original work for Holm et al. [1998] was done while the authors were at University of Copen-hagen, the two first authors as master’s students supervised by last author.Authors’ present addresses: J. Holm, Urbansgade 2, 1th, DK-2100 Copenhagen, Denmark; de Licht-enberg, Fogedmarken 12, 2tv, DK-2200 Copenhagen, Denmark, e-mail: [email protected]; M. Thorup,AT&T Labs—Research, Shannon Laboratory, 180 Park Avenue, Florham Park, NJ 07932, e-mail:[email protected] tomake digital/hardcopy ofpart or allof this work for personal or classroomuse is grantedwithout fee provided that the copies are not made or distributed for profit or commercial advantage,the copyright notice, the title of the publication, and its date appear, and notice is given that copyingis by permission of the Association for Computing Machinery (ACM), Inc. To copy otherwise, torepublish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.C°2001 ACM 0004-5411/01/0700-0723 $5.00Journal of the ACM, Vol. 48, No. 4, July 2001, pp. 723–760.724 J. HOLM ET AL.Likepriorityqueues,dynamicgraphalgorithmsmaybothbeofdirectinterest,andof interest as data structures within algorithms for static problems. As an exampleof direct usage, Frederickson [1985] suggests using a dynamic minimum spanningtree algorithm to maintain how heavily loaded links we need to use to get fromone vertex to another in a communications networks. As an example of usage asdata structures, Gabow et al. [1999] use dynamic 2-edge connectivity to efficientlydetermine if a graph has a unique matching.We now formally define the problems considered and state our results. We areconsidering a fully dynamic graph G over a fixed vertex set V, |V|=n. Unlessotherwise stated, m is the current number of edges, which we assume is 0 whenwe start. Most of the time bounds presented are amortized, meaning that theyare averaged over all operations performed. This is particularly justified when ourfully dynamic algorithms are used as data structures inside static algorithms wherewe only care about the total running time. We are striving for time bounds thatare polylogarithmic in n. Here polylogarithmic bounds are considered feasible fordynamic problems in the same way as polynomial bounds are considered feasiblefor static problems.For the fully dynamic connectivity problem, the updates may be interspersed withconnectivity queries, asking whether two given vertices are connected in G. Theconnectivity problem reduces to the problem of maintaining a spanning forest (aspanning tree for each component) in that if we can maintain any spanning forestF for G at cost O(t(n) log n) per update, then, using the dynamic trees of Sleatorand Tarjan [1983], we can answer connectivity queries in time O(log n/log t(n)).In this article, we present a very simple deterministic algorithm for maintaining aspanning forest in a graph in amortized time O(log2n) per update. Connectivityqueries are then answered in time O(logn/log log n).In the fully dynamic minimum spanning forest problem, we have weights on theedges, and we wish to maintain a minimum spanning forest F of G, that is, aminimum spanning tree for each component of G. Thus, in connection with anyupdate to G, we need to respond with the corresponding updates for F,ifany.Wepresent a deterministic algorithm for maintaining a minimum spanning forest F inO(log4n) amortized timeperoperation.Applyingthe dynamic trees technique fromSleator and Tarjan [1983] to the minimum spanning forest F,inO(log n/log logn)time, we can for any pair of vertices find the heaviest edge between them in F,which is also the heaviest edge needed to get between the vertices in G.A bridge in a graph is an edge whose removal disconnects some component. Agraph is 2-edge connected if and only if it is connected and contains no bridges. The2-edge connected components are the maximal 2-edge connected subgraphs, andtwo vertices v and w are 2-edge connected if and only if they are in the same 2-edgeconnected component, or equivalently, if and only if v and w are connected by twoedge-disjoint paths. In the fully dynamic 2-edge connectivity problem, the edgeupdates may be interspersed with queries asking whether two given vertices are2-edge connected. We present a deterministic algorithm supporting all operationsin O(log4n) amortized time per operation. The algorithm is easily augmented withsearches for bridges.Anarticulationpoint in a graph is a vertexwhoseremovaldisconnectssomecom-ponent. A graph is biconnected if and only if it is connected and has no articulationpoints. The biconnected components are the maximal biconnected subgraphs, andtwo vertices v and w are biconnected if and only if they are in the same