Randomized fully dynamic graph algorithms with polylogarithmic time per operation.
This paper solves a longstanding open problem in fully dynamic algorithms: We present the first fully dynamic algorithms that maintain connectivity, bipartiteness, and approximate minimum spanning trees in polylogarithmic time per edge insertion or deletion. The algorithms are designed using a new dynamic technique that combines a novel graph decomposition with randomization. They are Las-Vegas type randomized algorithms which use simple data structures and have a small constant factor.Let n denote the number of nodes in the graph. For a sequence of &OHgr;(m0) operations, where m0 is the number of edges in the initial graph, the expected time for p updates is     O(p log3 n) (througout the paper the logarithms are based 2) for connectivity and bipartiteness. The worst-case time for one query is O(log n/log log n). For the k-edge witness problem (Does the removal of k given edges disconnect the graph?) the expected time for p updates is O(p log3 n) and the expected time for q queries is O(qk log3 n). Given a graph with k different weights, the minimum spanning tree can be maintained during   a   sequence of p updates in expected time O(pk log3 n). This implies an algorithm to maintain a 1 + &egr;-approximation of the minimum spanning tree in expected time O((p log3 n logU)/&egr;) for p updates, where the weights of the edges are between 1 and U.
Introduction
In many areas of computer science, graph algorithms play an important role: Problems modeled
by graphs are solved by computing a property of the graph. If the underlying problem instance
changes incrementally, algorithms are needed that quickly compute the property in the modified
graph. Algorithms that make use of previous solutions and, thus, solve the problem faster than
recomputation from scratch are called fully dynamic graph algorithms. To be precise, a fully
dynamic graph algorithm is a data structure that supports the following three operations: (1)
insert an edge e, (2) delete an edge e, and (3) test if the graph fulfills a certain property, e. g. are
two given vertices connected.
Department of Computer Science, Cornell University, Ithaca, NY. Email: mhr@cs.cornell.edu. Author's Maiden
Name: Monika H. Rauch. This research was supported by an NSF CAREER Award.
y Department of Computer Science, University of Victoria, Victoria, BC. Email: val@csr.uvic.ca. This research
was supported by an NSERC Grant.
1 Throughout the paper the logarithms are base 2.
Previous Work. In recent years a lot of work has been done in fully dynamic algorithms (see [1, 3,
4, 6, 7, 8, 10, 11, 13, 16, 17, 19] for connectivity-related work in undirected graphs). There is also a
large body of work for restricted classes of graphs and for insertions-only algorithms. Currently the
best time bounds for fully dynamic algorithms in undirected n-node graphs are: O(
n) per update
for a minimum spanning forest [3]; O(
n) per update and O(1) per query for connectivity [3];
O(
log n) per update and O(log 2 n) per query for cycle-equivalence ("Does the removal of the
given 2 edges disconnect the graph?") [11]; O(
n) per update and O(1) per query for bipartiteness
("Is the graph bipartite?") [3].
There is a lower bound in the cell probe model
of\Omega\Gamma/32 n= log log n) on the amortized time per
operation for all these problems which applies to randomized algorithms [9, 11]. In [1] it is shown
that the average update time of (a variant of) the above connectivity and bipartiteness algorithms
is O(n=
m+ log n) if the edges used in updates are chosen uniformly from a given edge set. Thus,
for dense graphs their average performance nearly matches the lower bound.
In planar graphs fully dynamic algorithms for minimum spanning forest and connectivity are
given in [5] that are close to the lower bound: they take time O(log 2 n) per deletion and O(log n)
per insertions and query. However, the constant factor of these algorithms is quite large [5]. Thus,
the following questions were posed as open questions in [4, 5]:
(1) Can the above properties be maintained dynamically in polylogarithmic time in (general)
(2) Is the constant factor in the fully dynamic algorithms small such that an efficient implementation
is possible?
New Results. This paper gives a positive answer to both questions. It presents a new technique
for designing fully dynamic algorithms with polylogarithmic time per operation and applies this
technique to the fully dynamic connectivity, bipartiteness, 1+ffl-approximate minimum spanning
trees, and cycle-equivalence problem. The resulting algorithms are Las-Vegas type randomized
algorithms which use simple data structures and have a small constant factor.
For a sequence of \Omega\Gamma is the number of edges in the initial
graph the following amortized expected update times and worst-case query times are achieved:
1. connectivity in update time O(log 3 n) and query time O(log n= log log n);
2. bipartiteness in update time O(log 3 n) and query time O(1);
3. minimum spanning tree of a graph with k different weights in update time O(k log 3 n);
As an immediate consequence of these results we achieve faster fully dynamic algorithms for
the following problems:
1. An algorithm to maintain a 1+ffl-approximation of the minimum spanning tree in expected
time O((p log 3 n log U)=ffl) for p updates, where the weights of the edges are between 1 and U .
2. An algorithm for the k-edge witness problem ("does the removal of the given k edges disconnect
the graph?") in update time O(log 3 n) and amortized expected query time O(k log 3 n).
Note that cycle-equivalence is equivalent to the 2-edge witness problem.
3. A fully dynamic algorithm for maintaining a maximal spanning forest decomposition of order
k of a graph in time O(k log 3 n) per update by keeping k fully dynamic connectivity data
structures.
A maximal spanning forest decomposition of order k is a decomposition of a graph into k
edge-disjoint spanning forests F such that F i is a maximal spanning forest of G
. The maximal spanning forest decomposition is interesting since [ i F i is a graph
with O(kn) edges that has the same k-edge connected components as G [15].
Additionally we use the data structures to present simple deterministic algorithms that maintain
minimum spanning trees and connectivity fully dynamically. The amortized time per update for
the minimum spanning tree algorithm is O(
log n), which can be improved to O(
log n) using
the sparsification technique [4]. The amortized time per update for the connectivity algorithm is
O(
log n). Even though these algorithms do not improve on the running time of the best known
algorithms, they are interesting since they present a completely different approach than previous
algorithms and use only simple data structures. Additionally, the connectivity algorithm is the first
fully dynamic algorithm that does not use the sparsification technique and achieves a running time
of less than
m).
Main Idea. The new technique is a combination of a novel decomposition of the graph and
randomization. The edges of the graph are partitioned into O(log n) levels such that edges in
highly-connected parts of the graph (where cuts are dense) are on lower levels than those in loosely-
connected parts (where cuts are sparse). For each level i, a spanning forest is maintained for the
graph whose edges are in levels i and below. If a tree edge is deleted at level i, we sample edges on
level i such that with high probability either (1) we find an edge reconnecting the two subtrees or
(2) the cut defined by the deleted edge is too sparse for level i. In Case (1) we found a replacement
edge fast, in Case (2) we copy all edges on the cut to level recurse on level i + 1.
To our knowledge the only previous use of randomization in fully dynamic algorithms is are
(Monte-Carlo type) approximation algorithms for minimum cuts [12, 14].
This paper is structured as follows: Section 2 gives the fully dynamic connectivity algorithm,
Section 3 presents the results for k-weight minimum spanning trees, 1+ffl-approximate minimum
spanning trees, and bipartiteness. Section 4 and 5 contain the deterministic algorithms.
Randomized Connectivity Algorithm
2.1 A Deletions-Only Connectivity Algorithm
Definitions and notation: Let E) with jV m. We use the convention
that elements in V are referred to as vertices. Let l 1. The edges of G are
partitioned into l levels l such that [ ;. For each
i, we keep a forest F i of tree edges such that F i is a spanning forest of (V; [
l is a spanning tree of G and edges in E n F are referred to
as nontree edges. A spanning tree T on level i is a tree of F i .
All nontree edges incident to vertices in T are stored in a data structure that is described in
more detail below. The weight of T , denoted w(T), is the number of nontree edges incident to the
spanning tree, where edges whose both endpoints lie in the spanning tree are counted twice. The
size of T , denoted s(T), is the number of vertices in T . A tree is smaller than another tree if its
size is no greater than the other's. We say level i is below level i + 1.
2.1.1 The Algorithm
Initially all edges are in E 1 , and we compute F 1 which is a spanning tree of G.
When an edge e is deleted, remove e from the graph containing it. If e is a tree edge, let i be
the level such that e 2 E i . Call Replace(e; i).
Let T be the level i tree containing edge e and let T 1 and T 2 be the two subtrees of T that resulted
from the deletion of e, such that s(T 1
2.
ffl Sample: We sample c log 2 m nontree edges of E i incident to vertices of T 1 for some appropriate
constant c. An edge with both endpoints in T 1 is picked with probability 2=w(T 1 ) and an
edge with one endpoint in T 1 is picked with probability 1=w(T 1 ).
Case 1: Replacement edge found: If one of the sampled edges connects T 1 to T 2 then add it
to all F j , j - i.
ffl Case 2: Sampling unsuccessful: If none of the sampled edges connects T 1 and T 2 , search all
edges incident to T 1 and determine g.
choose one element of S and add it to F j , j - i.
remove the elements of S from E i , and insert them into
add one of the newly inserted edges to F j , j ? i.
- If l then do
2.1.2 Proof of Correctness
We first show that all edges are contained in [ i-l E i , i.e., when Replace(e; l) is called, and Case 2
occurs, no edges will be inserted into E l+1 . We use this fact to argue that if a replacement edge
exists, it will be found.
be the number of edges ever in E i .
Lemma 2.1 For all smaller trees T 1 on level i,
Proof: The proof follows [6]. When a tree is split into two trees and an endpoint of an
edge is contained in the smaller tree, the size of the tree which contains that endpoint has
been halved. Thus, over the course of the algorithm, each endpoint of an edge is inci dent
to a smaller tree at most log n times in a given level, and, for all such trees T 1 on level i,
Lemma 2.2 For any i, m i - m=c 0i\Gamma1 .
Proof: We show the lemma by induction. It clearly holds for Assume it holds for
summed over all smaller trees T 1 , P
log n) edges are added to E i .
By Corollary 2.1, P
is the total number of edges ever in level
implies that the total number of edges in E i is no greater than m=c
Choosing c observing that edges are never moved to a higher level from a level with
less than 2 log n edges gives the following corollary.
Corollary 2.3 For are contained in some E i , i - l.
The following relationship, which will be useful in the running time analysis, is also evident.
Corollary 2.4 P
Theorem 2.5 F i is a spanning forest of (V; [
Proof: Initially, this is true, since we compute F 1 to be the spanning tree of
Consider the first time it fails, when a tree edge e is deleted, and a replacement edge
exists but is not found. By Corollary 2.3, the replacement edge lies in some
Let i be the minimum level at which a replacement edge exists. Let e be in E k . Then
we claim i - k. Assume not. Then let fr; sg be a replacement edge at level i. Since r and s
are connected, there is a path from r to s in F i . Since e 2 F k , e is not in this path. Hence,
sg is not a replacement edge for e. Thus k - i and Delete(e; i) will be called.
Either a replacement edge will be found by sampling or every edge incident to T 1 will be
examined. We claim that every replacement edge fr; sg is incident to T 1 . Suppose it is not.
By assumption, there is a path from r to s in [ j-i F j . If this path includes e then either r
or s is in T 1 . If it doesn't include e, then fr; sg forms a cycle with F \Gamma e contradicting the
assumption that fr; sg is a replacement edge.
2.1.3 The Euler Tour Data Structure
In this subsection we present the data structure that we use to implement the algorithm of the
previous section efficiently. We encode an arbitrary tree T with n vertices using a sequence of
symbols, which is generated as follows: Root the tree at an arbitrary vertex. Then call ET (root),
where ET is defined as follows:
visit x;
for each child c of x do
visit x.
Each edge of T is visited twice and every degree-d vertex d times, except for the root which is
visited times. Each time any vertex u is encountered, we call this an occurrence of the vertex
and denote it by o u .
New encodings for trees resulting from splits and joins of previously encoded trees can easily
be generated. Let ET (T ) be the sequence representing an arbitrary tree T .
Procedures for modifying encodings
1. To delete edge fa; bg from T : Let T 1 and T 2 be the two trees which result, where a 2 T 1
encountered in the two traversals
of fa; bg. If
and
then
. Thus ET (T 2 ) is given by
the interval of ET (T ) splicing out of ET (T ) the sequence
2. To change the root of T from r to s: Let any occurrence of s. Splice out the first
part of the sequence ending with the occurrence before remove its first occurrence (o r ),
and tack it on to the end of the sequence which now begins with . Add a new occurrence
s to the end.
3. To join two rooted trees T and T 0 by edge e: Let Given
any occurrences o a and create a new occurrence o an and splice the sequence
an into ET (T ) immediately after o a .
If the sequence ET (T ) is stored in a balanced search tree of degree b, and height O(log n= log b)
then one may insert an interval or splice out an interval in time O(b log n= log b), while maintaining
the balance of the tree, and determine if two elements are in the same tree, or if one element
precedes the other in the ordering in time O(log n=b).
Aside from lists and arrays, the only data structures used in the connectivity algorithm are
trees represented as sequences which are stored in balanced b-ary search trees. We next describe
these data structures.
Data structures: We have two options for storing the nontree edges: the first is simpler and is
explained here. The second shaves off a factor of log log n from the update time by reducing the
cost of sampling. It is described in the last subsection of this section.
For each spanning tree T on each level i ! l, each occurrence of ET (T ) is stored in a node of
a balanced binary search tree we call the ET(T)-tree. For each tree T on the last level l, ET (T )
is stored in a balanced (log n)-ary search trees. Note that there are no nontree edges on this level.
For each vertex arbitrarily choose one occurrence to be the active occurrence of u.
With the active occurrence of each vertex v, we keep an (unordered) list of nontree edges in
level i which are incident to v, stored as an array. Each node in the ET-tree contains the number of
nontree edges and the number of active occurrences stored in its subtree. Thus, the root of ET (T )
contains the weight and size of T .
In addition to storing G and F using adjacency lists, we keep some arrays and lists:
ffl For each vertex and each level, a pointer to the vertex's active occurrence on that level.
ffl For each tree edge, for each level k such that e 2 F k , pointers to each of the four (or three, if
an endpoint is a leaf) occurrences associated with its traversal in F k ;
ffl For each nontree edge, pointers to the locations in the two lists of nontree edge containing
the edge and the reverse pointers.
ffl For each level i, a list containing a pointer to each root of a ET(T)-tree, for all spanning trees
T at level i, and for each root a pointer back to the list;
ffl For each level i, a list of tree edges in E i and for each edge a pointer back to its position in
the list.
2.1.4 Implementation
Using the data structures described above, the following operations can be executed on each spanning
tree on each level. Let T be a spanning tree on level i.
ffl tree(x; i): Return a pointer to ET (T ) where T is the spanning tree of level i that contains
vertex x.
ffl nontree edges(T Return a list of nontree edges stored in ET (T ); each edge is returned once
or twice.
Randomly select a nontree edge of E i that has at least one endpoint in T ,
where an edge with both endpoints in T is picked with probability 2=w(T ) and an edge with
exactly one endpoint in T is picked with probability 1=w(T ). Test if exactly one endpoint is
in T , and if so, return the edge.
ffl insert tree(e; i): Join by e the two trees on level i, each of which contains an endpoint of e.
ffl delete tree(e; i): Remove e from the tree on level i which contains it.
ffl insert nontree(e; i): Insert the nontree edge e into E i .
ffl delete nontree(e): Delete the nontree edge e.
The following running times are achieved using a binary search tree: tree, sample&test,
insert non tree, delete non tree, delete tree, and insert tree in O(log n) and nontree edges(T ) in
O(m 0 log n), where m 0 is the number of moved edges. On the last level l, when a (log n)-ary tree
is used, the running time of delete tree and insert tree is increased to O(log 2 n= log log n) and the
running time of tree is reduced to O(log n= log log n). We describe the implementation details of
these operations.
tree(x,i): Follow the pointer to the active occurrence of x at level i. Traverse the path in the
ET (T )-tree from the active occurrence to the root and return a pointer to this root.
nontree edges(T): Traverse all nodes of ET (T ) and output every non-empty list of nontree edges
encountered at a node.
Let T be a level i tree. Pick a random number j between 1 and w(T ) and find
the j th nontree edge fu; vg stored in the ET (T ). If tree(u; l) 6= tree(v; l) then return the edge.
insert tree(e,i) Determine the active occurrences of the endpoints of e on level i and follow
Procedure 3 for joining two rooted trees, above. Update pointers to the root of the new tree and
the list of tree edges on level i.
delete tree(e,i): Let vg. Determine the four occurrences associated with the traversal of
e in the tree on level i which contains e and delete e from it, following Procedure 1, above. Update
pointers to the roots of the new trees, the list of tree edges, and (if necessary) the active occurrences
of u and v.
insert nontree(e,i): Determine the active occurrences of the endpoints of e on level i and add e
to the list of edges stored at them.
delete nontree(e): Follow the pointers to the two locations of e in lists of non-tree edges and
remove e.
Using these functions, the deletions only algorithm can be implemented as follows.
To initialize the data structures: Given a graph G compute a spanning forest of G. Compute
the ET (T ) for each T in the forest, select active occurrences, and set up pointers as described
above. Initially, the set of trees is the same for all levels. Then insert the nontree edges with the
appropriate active occurrences into level 1 and compute the number of nontree edges in the subtree
of each node.
To answer the query: "Are x and y connected?": Test if tree(x;
To update the data structure after a deletion of edge e=fu,vg: If e is in E i , then do
delete tree(e;
If e is not a tree edge, execute delete nontree(e).
2.
Repeat times.
Case 1: Replacement edge e 0 is found
delete nontree(e 0 );
Case 2: Sampling unsuccessful
for each edge fu; vg 2 nontree
if tree(u; l) 6= tree(v; l) then add fu; vg to S.
fedges with exactly one endpoint in T 1 g g.
Case 2.1: jSj - w(T 1 )=(2c 0 log n)
Select one e
Case 2.2:
Choose one edge e 0 2 S and remove it from
for every edge e 00 2 S do delete non tree(e 00 ); insert nontree(e 00
Case 2.3:
2.1.5 Analysis of Running Time
We show that the amortized cost per deletion is O(log 3 n) if there are m deletions.
In all cases where a replacement edge is found, O(log n) insert tree operations are executed,
costing O(log 2 n). In addition:
Case 1: Sampling is successful. The cost of sample&test is O(log n) and this is repeated
O(log 2 n) times, for a total of O(log 3 n).
Case 2: Sampling is not successful or w(T 1 We refer to the executing nontree
and the testing of each edge as the cost of gathering and testing the nontree edges. The first operation
costs O(log n) per nontree edge and the second is O(log n= log log n) per nontree edge, for a
total cost of O(w(T 1 ) log n). Now there are three possible cases.
Case 2.1: jSj - w(T 1 )=(2c 0 log n). If w(T 1 the cost of gathering and
testing to the delete operation. Otherwise, the probability of this subcase occurring is
and the total cost of this case is O(w(T 1 ) log n). Thus
this contributes an expected cost of O(log n) per operation.
Case 2.2 and 2.3: jSj ! w(T 1 )=(2c 0 log n) Each delete nontree, insert nontree, and tree costs
O(log n), for a total cost of O(w(T 1 ) log n). In this case tree(u; i) and tree(v; i) are not reconnected.
Note that only edges incident to the smaller tree T 1 are gathered and tested. Thus, over the course
of the algorithm, the cost incurred in these cases on any level i is O(
where the sum
is taken over all smaller trees T 1 on level i. From Lemma 2.1, we have the P
From Corollary 2.4, P
giving a total cost of O(m log 2 n).
2.2 A Fully Dynamic Connectivity Algorithm
2.2.1 The Algorithm
Next we also consider insertions. When an edge fu; vg is inserted into G, add fu; vg to E l . If u
and v were not previously connected in G, i.e., tree(u; l) 6= tree(v; l), add fu; vg to F l .
We let the number of levels l = d2 log ne. A rebuild of the data structure is executed periodically.
A rebuild of level i, for i - 1, is done by a move edges(i) operation, which moves all tree and nontree
edges in E j for Also, for each j ! i, all tree edges in E j are inserted into all F k ,
that after a rebuild at level i, contains no edges, and F
i.e., the spanning trees on level j - i span the connected components of G.
After each insertion, we increment I, the number of insertions modular 2 d2 log ne since the start
of the algorithm. Let j be the greatest integer k such that 2 k jI. After an edge is inserted, a rebuild
of level l executed. If we represent I as a binary counter whose bits are b
b 0 is the most significant bit, then a rebuild of level i occurs each time the i th bit flips to 1.
2.2.2 Proof of Correctness
The proof of correctness is the same as the one for the deletions-only case, except that we must
set the value of l to d2 log ne and alter the argument which shows that all edges are contained in
We define an i-period to be any period beginning right after a rebuild of levels j - i, or the
start of the algorithm and ending right after the next rebuild of level j 0 - i. I.e., an i-period starts
right after the flip to 1 of some bit j - i, or the start of the algorithm and ends with next such
flip. Note that there are two types of i-periods: (A) begins immediately after a rebuild of level
all edges from E i are moved to some E j with flips to 1); (B) begins
immediately after a rebuild of level i, i.e. all edges from [ are moved into E i (b i flips to 1).
It is easy to see that an i-1-period consists of two parts, one type A i-period, followed by one
since any flip to 1 by some bit b j , must be followed by a flip of b i to 1
before a second bit b j 0 , flips to 1.
Theorem 2.6 Let a i be the number of edges in E i during an i-period. Then a
Proof: By a proof analogous to that of Lemma 2.1 we have:
Lemma 2.7 For all smaller trees T 1 on level i which were searched between two consecutive
rebuilds of levels
We now bound a i . Note that we may restrict our attention to the edges which are moved
during any one i-1-period since E i is empty at the start of each i-1 period.
Thus, an edge is in E i either because it was passed up from E during one i-1-period
or moved there in a single rebuild of level i.
was empty at the start of the i-1-period, any edge moved to E i during
the rebuild of level i was passed up from E i\Gamma1 to E i and then to E i\Gamma1 during the type
A i-period (i.e., the first part of the i-1-period) or was inserted into G during the type A
i-period. We have
a
where h i\Gamma1 is the maximum number of edges passed up from E i\Gamma1 to E i during a single
(i.e., an A i-period followed by a B i-period) and b i is the number of edges
inserted into G during a single i-period.
The number of edges inserted into G during an i-period is 2 l\Gammai\Gamma1 .
To bound h i we use Lemma 2.7 to bound P
summed over all smaller trees T 1
which are searched on level during an As in the proof of Lemma 2.2, we
can now bound h. Choosing
Substituting for h and b yields
a
Choosing log ne and noting that a 1 ! n 2 , an induction proof shows that a i !
This implies a l ! 2 and edges are never passed up to a l+1 . We have:
Corollary 2.8 For log ne all edges of E are contained in some E i , i - l.
2.2.3 Analysis of the Running Time.
To analyze the running time, note that the analysis of Case 1 and Case 2.1, above, are not affected
by the rebuilds. However, (1) we have to bound the cost incurred during an insertion, i.e. the cost
of the operation move edges and (2) in Case 2.2 and 2.3, the argument that O(m i log n) edges are
gathered and tested (using nontree edges and tree) on level i during the course of the algorithm
must be modified.
The cost of (1), i.e. the cost of executing move edges(i) is the cost of moving each tree edge
and each nontree edge in and the cost of updating all the F k ,
To analyze the first part, we note that each move of an edge into E i costs O(log n) per edge.
The number of edges moved is no greater than P
Thus the cost incurred is
The cost of inserting one tree edge into any given level is O(log n) per edge. A tree edge is
added only once into a level, since a tree edge is never passed up. Thus this cost may be charged
to the edge for a total cost of O(log 2 n) per edge.
We analyze the cost of (2).
For been inserted since the start of the algorithm then no
rebuilds have occurred at level i or lower, and the analysis for level i of the deletions-only argument
holds. That is, the costs incurred on level i is bounded above by O(m log 2 n=c is the
number of edges in the initial graph.
Applying Lemma 2.7, we conclude that the cost for the gathering and testing of edges from all
smaller trees T 1 on level i during an i-period is O(2a i log n   log
For l, we note that since there are O(1) edges in E l at any given time, and since the cost is
O(log n) per edge for gathering and testing, the total cost for each instance of gathering and testing
on this level is O(log n).
We use a potential function argument to charge the cost of (1) and (2) to the insertions. Each
new insertion contributes c 00 log 2 n tokens toward the bank account of each level, for a total of
\Theta(log 3 n) tokens. Since an i-period occurs every n 2 =2 i insertions, the tokens contributed by these
insertions can pay for the O(n 2 log 2 n=2 i ) cost of the gathering and testing on level i during the
i-period and the O(n 2 log n=2 i ) cost of move edges(i) incurred at most once during the i-period.
2.3 Improvements
In this section, we present a simple "trick" which reduces the cost of testing all nontree edges
incident to a smaller tree T 1 to O(1) per edge so that the total cost of gathering and testing edges
incident to T 1 is O(1) per edge.
2.3.1 Constant Time for Gathering and Testing
As noted above, since the nontree edges incident to an ET-tree are available as a list, the time
needed to retrieve these edges is O(1) per edge. One can also test each nontree edge in O(1) time,
i.e., determine the set S of all nontree edges which contain only one endpoint, by running through
the list three times. For each edge in the list, initialize the entry of an n \Theta n array. Then use
these entries to count the number of times each edge appears in the list. Traverse the list again
and add to S any edge whose count is one.
2.3.2 Constant Query and Test Time for Deletions-Only Algorithms
We note that determining whether two vertices i and j are in the same component, i.e., is
tree(j), can be speeded up to O(1) for the deletions-only algorithm. A component is split when
Replace(e; l) is called and no replacement edge is found. In that case, label the nodes of the smaller
component T 1 with a new label. The cost of doing so is proportional to the size of T 1 . Over the
course of the algorithm, the cost is O(n log n) since each node appears in a smaller component no
more than log n times. Then have the same label.
This improvement does not affect the asymptotic running time of the randomized connectivity
algorithm, as that is dominated by the cost of the random sampling. However it will be used in
the deterministic algorithms presented later in the paper.
Randomized Algorithms for Other Dynamic Graph Problems
In this section, we show that some dynamic graph problems have polylogarithmic expected up-date
time, by reducing these problems to connectivity and we give an alternative algorithm for
maintaining the minimum spanning tree.
3.1 A k-Weight Minimum Spanning Tree Algorithm
The k-weight minimum spanning tree problem is to maintain a minimum spanning forest in a
dynamic graph with no more than k different edgeweights at any given time.
E) be the initial graph. Compute the minimum spanning forest F of G. We define
a sequence of subgraphs G
fedges with weight of rank ig [ F . If initially, there are l ! k distinct edgeweights, then
are called "extras". The spanning forests of each G i are maintained as
in the connectivity algorithm. These forests and F are also stored in dynamic trees. The subgraphs
are ordered by the weight of its edgeset and stored in a balanced binary tree.
To insert edge fu; vg into G: determine if u and v are connected in F . If so, find the maximum
cost edge e on the path from u to v in F . If the weight of e is greater than the weight of fu; vg,
replace e in F by fu; vg. If u and v were not previously connected, add fu; vg to F . Otherwise, just
add fu; vg to E j where j is the rank of the weight of fu; vg. If fu; vg is the only edge of its weight
in G, then create a new subgraph by adding fu; vg to an extra and inserting it into the ordering of
the other G i . Update the E i to reflect the changes to F .
To delete edge fu; vg from G: Delete fu; vg from all graphs containing it. To update F : If
fu; vg had been in F , then a tree T in F is divided into two components. Find the minimum i
such that u and v are connected in G i using binary search on the list of subgraphs. Now, search
the path from u to v in the spanning forest of G i to find an edge crossing the cut in T . Use binary
Let x be a midpoint of the path. Recurse on the portion of the path between u and x if u
and x are not connected in F ; else recurse on the path between x and v.
Correctness: When an edge fu; vg is inserted and its cost is not less than the cost of the
maximum cost edge on the tree path between u and v, then the minimum spanning forest F is
unchanged. If the cost of fu; vg is less than the cost of the maximum cost edge e 0 on the tree path
between u and v, then replacing e 0 by fu; vg decreases the cost of the minimum spanning tree by
the maximum possible amount and gives, thus, the minimum spanning tree of G [ fu; vg.
Analysis of Running Time: The algorithm (1) determines how F has to be changed, and (2)
updates the data structures. (1) After an insertion the maximum cost edge on the tree path between
u and v can be determined in time O(log n) using the dynamic tree data structure of F . After a
deletion, it takes time O(log 2 n= log log n) to find the minimum i such that u and v are connected
in G i , since a connectivity query on a level takes time O(log n= log log n). The midpoint of the
tree path between u and v in G i can be determined in time O(log n) using the dynamic tree data
structure of the spanning tree of G i . The algorithm recurses at most log n times to determine the
replacement edge for fu; vg, for a total of O(log 2 n).
(2) The insertion or deletion of fu; vg into E i , where i is the rank of the weight of fu; vg, takes
amortized expected time O(log 3 n). If F changes, one additional insertion and deletion is executed
in every E j . For each update there are a constant number of operations in the dynamic tree of F
and of the spanning tree of every E j , each costing O(log n). Thus, the amortized expected update
time is O(k log 3 n).
3.2 ffl-Approximate Minimum Spanning Tree Algorithm
Given a graph with weights between 1 and U , a 1+ffl-approximation of the minimum spanning tree is
a spanning tree whose weight is within a factor of 1+ffl of the weight of the optimal. The problem of
maintaining a 1+ffl approximation is easily seen to be reducible to the k-weight MST problem, where
a weight has rank i if it falls in the interval [(1
This yields an algorithm with amortized cost O((log 3 n log U)=(ffl log log n)).
3.3 A Bipartiteness Algorithm
The bipartite graph problem is to answer the query "Is G bipartite?" in O(1) time, where G is a
dynamic graph.
We reduce this problem to the 2-weight minimum spanning tree problem. We use the fact that
a graph G is bipartite iff given any spanning forest F of G, each nontree edge forms an even cycle
with F . Call these edges "even edges" and the remaining edges "odd". We also use the fact that
if an edge e in F is replaced with an even edge then the set of even edges is preserved. Let C be
the cut in F induced by removing e. If e is replaced with an odd edge then for each nontree edge
e 0 which crosses C the parity of e 0 changes. We replace an edge by an odd replacement edge only
if there does not exists an even replacement edge. Thus, the parity of an even edge never changed.
F is stored as a dynamic tree.
Our algorithm is: generate a spanning forest F of the initial graph G. All tree and even nontree
edges have weight 0. Odd edges have weight 1. If no edges have weight 1, then the graph is
bipartite.
When an edge is inserted, determine if it is odd or even by using the dynamic tree data structure
of F , and give it weight 1 or 0 accordingly.
When an edge is deleted, if it is a tree edge, and if it is replaced with an odd edge (because
there are no weight 0 replacements), remove the odd edge and find its next replacement, remove
that, etc. until there are no more replacements. Then relabel the replacement edges as even and
add them back to G.
Correctness: When an edge is inserted, the algorithm determines if it is even or odd. If an edge
is deleted, we replace it by an even edge if possible. This does not affect the parity of the remaining
edges. If no even replacement edge exists, but an odd replacement edge, the parity of every edge
on the cut changes. However, since no even edge exists on the cut, it suffices to make all odd edges
into even edges.
Analysis of Running Time: An even edge never becomes odd. Thus, the weight of an edge
changes at most once, which shows that an insertion of an edge causes the edge to be added to the
data structure at most once with weight 1 and at most once with weight 0. The deletion of an edge
leads to the removal of the edge from the data structure. Thus, amortized expected update time is
O(log 3 n).
4 A Deterministic Minimum Spanning Tree Algorithm
In this section we present a fully dynamic deterministic minimum spanning tree algorithm with
amortized time O(
log n) per operation, where m is the current number of edges in G. We
note that the technique of sparsification [4], when applied on top of this algorithm, will yield an
algorithm with O(
log n) amortized time per operation.
4.1 A Deletions-Only Minimum Spanning Tree Algorithm
The data structures which we use are very similar to those of the randomized connnectivity algo-
rithm. Instead of random sampling, we always exhaustively search edges incident to the smaller
components. Edges are stored in p
levels, according to their weight and do not move between
levels. A deletions-only data structure is kept for "old" edges. Newly inserted edges are kept in
a separate level. Periodically, a rebuild is executed in which the deletions-only data structure is
revised to include the newly inserted edges.
E) with jV m. Rank the edges by weight. The edges of G are
partitioned into l levels l such that E i for i - l contains all edges with rank j, where
m. Compute a minimum spanning forest F of G. For each i, we keep a forest
F i of tree edges such that F i is a minimum spanning forest of (V; [
. Note that F i n F
4.1.1 The Algorithm
To update the data structure after a deletion of edge e=fu,vg: If e is not a tree edge,
then do delete nontree(e). If e is a tree edge in E i , then do delete tree(e;
Replace(u; v; i).
else
Gather and test nontree edges incident to T 1
Case 1: Replacement edge is found
Let e 0 be a minimum weight replacement edge;
Case 2: No Replacement edge is found
4.1.2 Implementation and Analysis of Running Time
We use the same data structure as in the randomized algorithm, storing all nontree edges in E i in
the appropriate ET-tree on level i. Each ET-tree is stored as a binary tree; all nontree edges are
stored in NT-lists, so that gathering and testing of all edges incident to T 1 may be done in w(T )
time. (See Improvements Section 2.3.1, above.)
When a tree edge is deleted and a replacement edge is sought, the total cost of gathering and
testing of nontree edges in a given level i is charged to the deletion, if a replacement edge is found
in or to the level, if not. We consider the latter case first. Then T 1 becomes a new component
of F i . The cost of gathering and testing edges incident to T 1 is O(w(T 1 )). On a given level,
log n (see Lemma 2.1). Over all levels, the total cost is O(m log n).
The cost of gathering and testing in the level in which the replacement edge is found is no
greater than the cost of gathering and testing every edge in that level, or O(
m).
In addition, for each tree edge, no more than p
insert tree operations are executed, once per
level, for a total cost of O(
log n). The cost of delete nontree is O(log n).
The cost is thus O(
log n) per edge deletion plus a total cost of O(m log n) during the course
of the algorithm.
4.2 A Fully Dynamic Minimum Spanning Tree Algorithm
4.2.1 The Algorithm
A partial rebuild of the data structure is executed after p
is the number
of edges which were in the graph at the last rebuild, or initially, if there has been no rebuild. These
edges are referred to as old edges and, if they are still in G, are stored in the deletions-only data
structure described above. All newly inserted edges are stored in a separate set E l+1 . Then F l
is a minimum spanning tree consisting only of the old edges, i.e., of G(V; [ F be a
minimum spanning tree of G(V; E), i.e., of old and new edges. We store F in a dynamic tree data
structure. For each E i with i - l we keep a list of its edges ordered by rank.
To rebuild: When the number of updates (insertions or deletions) since the last rebuild or the
start of the algorithm reaches p
reset to the current number of edges in the graph.
Insert each edge in E l+1 into an appropriate E i , for i - l and redistribute the old edges among the
so that for i - l, E i contains all edges with rank j, where (i \Gamma 1) p
All edges are
now "old edges". If tree edge of level i moves to level i 0 then add the edge to all levels
or remove the edge from all levels i
To delete an edge e from G: If e is an old tree edge, then update the deletions-only data
structure. If e does not belong to F , stop. Otherwise, delete vg from F and find the
minimum cost edge e 0 with exactly one endpoint in T 1 in E l+1 . Add to F the smaller-cost edge of
e 0 and of the replacement edge in the deletions only data structure (if existent).
To insert an edge e to G: Add the edge to E l+1 and test if it replaces an edge of F . That is,
use the dynamic tree to find the heaviest edge in the path between e's endpoints, if there is such a
path, and determine if e is lighter. If yes, modify F accordingly.
4.2.2 Analysis of Running Time
The cost of an edge insertion is O(log n), since it consists of constant number of operations on the
dynamic tree data structure.
The cost of an edge deletion may include the cost of updating the dynamic tree data structure,
which is O(log n); the cost of testing edges in E l+1 , which is O(
log n); and the cost of updating
the deletions-only data structure. We show how to bound the latter.
The cost involved in the deletions-only data structure between rebuilds is given by the analysis
in Section 4.1.2 : O( p
per deletion of a tree edge plus an overall cost of O(m 0 log n)
between rebuilds, which is O(
log n) per update operation.
We bound next the cost of a rebuild. First we discuss adding the edges to the appropriate
level, then we discuss "rebalancing" the size of a level. Determining the appropriate level for an
edge takes time O(log n) using a binary search. Moving a nontree edge from E l+1 to E i with i - l
costs O(log n) per edge, for a total of O(
Moving a tree edge from E l+1 to E i with
requires the insertion of the edge into all levels j - i and costs O(
per edge, for a
total of O(m 0 log n). Any edge in E i , for i - l, is never moved by more than one level during the
"rebalancing", i.e., either into E This costs O(log n) per tree or non-tree edge. Thus
the time of a rebuild is O(m 0 log n).
The cost of a rebuild, when amortized over the p
which occur, is O( p
be the number of edges currently in the graph when an operation occurs. Since
the cost of this algorithm per edge deletion or insertion is O(
log n).
5 A Deterministic Connectivity Algorithm
The above minimum spanning tree algorithm can be easily converted into an algorithm for connectivity
with the same running time. In this section, we give an alternative connectivity algorithm
with O(
log n) amortized update time without the use of sparsification. The data structure used
here is similar to those used in the previously presented algorithms. There are two important dif-
ferences. As in the previous algorithm, edges are partitioned into levels Here, each level
contains at most p
edges, and levels are added as needed. That is, initially,
levels with
edges each are created. New edges are inserted into the highest level if it contains
less than p
edges, and into a newly created (empty) highest level, otherwise. The data structure
as a whole is never rebuilt; new levels are added one at a time. If all edges in a level have been
deleted, the level is discarded. We use the term level i to denote the ith non-empty level. As in the
previous algorithm, edges do not move between levels.
The F i are defined as before: For each i, we keep a forest F i of tree edges such that F i is
a spanning forest of (V; [ Here, the F i
are stored in "relaxed" versions of ET-trees, called RET-trees. Unlike the ET-trees used in the
previous algorithms, RET-trees have the following property: If an edge on level i is deleted and a
replacement edge is found on level j (i ! j), then only the RET-trees on levels
to be updated. This allows us to keep a larger number of levels.
5.1 The RET-Tree Data Structure
Let T be a spanning tree on level i and let C(T ) be the tree that is created from T by contracting
every spanning tree on level to one node. Each node of C(T ) is called a big node. Thus, all
edges of C(T ) belong to F i .
An RET(T)-tree consists of an ET-tree for the sequence ET (C(T )) where the list of edges at
the active occurrence of a vertex a is replaced
ffl A list Nodes(a) of all the vertices of G that have been contracted to form a, in the following
first all vertices that are incident to edges in E i , then all other vertices. At each vertex
v of G in Nodes(a) we keep (1) a list of all the edges of F i incident to v, (2) a list of all the
nontree edges incident to v, (3) the number of nontree edges incident to v, and (4) a pointer
to a.
ffl The number of edges incident to the vertices in Nodes(a).
In addition, we keep an ordered list of nonempty levels stored in a doubly linked list L and, for
each nonempty level, an array whose jth entry is a pointer to the location of the vertex j in the
Nodes-list on level i which contains j.
The operations for RET-trees are the same as those defined for ET-trees, with the omission of
sample&test, and the addition of two more operations defined below:
ffl big node(u; i): Return the big node on level i that contains vertex u.
The operation assumes that e is a deleted edge of F i , whose
endpoints are (still) contained in the same big node a on level i + 1. Let T 1 and T 2 be the
spanning trees of level i containing the endpoints of e, where T 1 is the smaller of these two
trees. Split a into two big nodes that represent
To implement big node(u; i), follow the pointer from level i, vertex u to the Nodes-list on level
which contains u, and the pointer from there to the big node containing u. Each call to big node
is dominated by the cost of finding level i in L, which takes time O(log n).
To implement split big the smaller of the two subtrees and let
vg. By traversing ET (C(T 1 )) on level i determine the set U of all vertices of G in T 1 .
Using big one node of U , determine the big node a that represents all nodes of
U . Remove each node in U from Nodes(a), create a new node b, and add all nodes of U into a new
(ordered) Nodes(b) list. Then update the number of edges incident to the nodes in Nodes(a) and
in Nodes(b) accordingly. A call to split big node takes time proportional to the number of vertices
in T 1 plus O(log n) for the call to big node.
The implementation of the ET-tree operations need only be modified slightly, and each has a
running time of O(log n). That is, in insert nontree(T ; e) and delete nontree(e) an endpoint of e
may be moved to the beginning or the end of the Nodes-list containing it. The implementation
of tree(x; i), nontree edges(T ), insert tree(e; i), and delete tree(e; i) are unchanged, except for a
constant number of calls to big node.
5.2 The Algorithm
To update the data structure after a deletion of edge e=fu,vg: If e is not a tree edge, execute
delete nontree(e). If e is a tree edge on level i, then delete tree(e; i) and call Replace(u; v; i).
if
Gather and test nontree edges incident to T 1
Case 1: Replacement edge e 0 is found
delete nontree(e 0 );
insert tree(e
Case 2: No Replacement edge is found
Let j be the next lowest nonempty level above i.
split big node(e; j).
Replace(u; v; j).
To update the data structure after an insertion of edge e=fu,vg: If the number of edges
in level(l) is p
then build a data structure for a new level and reset l to this new level. If u and
are connected then call insert nontree(e; tree(u; l)) else insert tree(e; l).
5.3 Implementation and Analysis of Running Time
To gather and test non-tree edges we store the nontree edges in NT-lists (see Section 2.3.1) so that
gathering and testing of all edges incident to T 1 may be done in time O(w(T 1 is the
number of nontree edges incident to T 1 .
We show that the amortized time per update operation is O(
log n). Since building a data
structure for a new level takes time O(n) and occurs every p
n insertions, the total time for all
insertions charge O(n=
n) to each insertion. Next we show that the total cost of all
deletions is O((m
log n), where m 0 is the number of edges in the initial graph and k is the
total number of update operations.
The search for a replacement edge takes time O(w(T 1 )). We separately consider the cost of
the search on the last level in which the search occurred (and either terminated successfully or
discontinued because there were no more levels) and the cost on the other levels where the search
occurred. The total cost of searches for the deletions on the last level is no more than p
per
search or O((m 0
log n). The total cost of searching on all levels where no replacement edge
is found is O(
summed over all T 1 which are created, on all levels. Applying Lemma 2.1,
we have a total cost of O((m
log n).
The cost of split big node can be charged to the the nodes in T 1 , for a total cost of n log n per
level. Since at most O((m
n) levels are created during the whole course of the algorithms,
the total cost of split big node is O((m
log n).
Thus the cost of update operations, when amortized over all updates is O(
log n), for
6

Acknowledgements

We are thankful for David Alberts for comments on the presentation.



--R

"Average Case Analysis of Dynamic Graph Algo- rithms"
"Main- tenance of a Minimum Spanning Forest in a Dynamic Planar Graph"
"Improved Sparsification"
"Sparsification - A Technique for Speeding up Dynamic Graph Algorithms"
"Separator Based Sparsification for Dynamic Planar Graph Algorithms"
"An On-Line Edge-Deletion Problem"
"Data Structures for On-line Updating of Minimum Spanning Trees"
"Ambivalent Data Structures for Dynamic 2-Edge-connectivity and k Smallest Spanning Trees"
"Lower Bounds for Fully Dynamic Connectivity Problems in Graphs"
"Fully Dynamic Algorithms for 2-Edge Connectivity"
"Fully Dynamic Cycle-Equivalence in Graphs"
"Approximating Minimum Cuts under Insertions"
"Sparse Certificates for Dynamic Biconnectivity in Graphs"
"Using Randomized Sparsification to Approximate Minimum Cuts"
"Linear time algorithms for finding a sparse k-connected spanning subgraph of a k-connected graph"
"Fully Dynamic Biconnectivity in Graphs"
"Improved Data Structures for Fully Dynamic Biconnectivity in Graphs"
"A data structure for dynamic trees"
"On Finding and Updating Spanning Trees and Shortest Paths"
--TR
A data structure for dynamic trees
Amortized analysis of algorithms for set union with backtracking
Maintenance of a minimum spanning forest in a dynamic plane graph
Fully dynamic algorithms for 2-edge connectivity
Complexity models for incremental computation
Separator based sparsification I.
Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and <i>k</i> Smallest Spanning Trees
SparsificationMYAMPERSANDmdash;a technique for speeding up dynamic graph algorithms
Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
Sampling to provide or to bound
An On-Line Edge-Deletion Problem
Improved Data Structures for Fully Dynamic Biconnectivity
Certificates and Fast Algorithms for Biconnectivity in Fully-Dynamic Graphs

--CTR
Mihai Ptracu , Erik D. Demaine, Lower bounds for dynamic connectivity, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
David Eppstein, Dynamic generators of topologically embedded graphs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
Glencora Borradaile , Philip Klein, An O (n log n) algorithm for maximum st-flow in a directed planar graph, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.524-533, January 22-26, 2006, Miami, Florida
Robert E. Tarjan , Renato F. Werneck, Self-adjusting top trees, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
Umut A. Acar , Guy E. Blelloch , Robert Harper , Jorge L. Vittes , Shan Leung Maverick Woo, Dynamizing static algorithms, with applications to dynamic trees and history independence, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
Camil Demetrescu , Giuseppe F. Italiano, Algorithmic Techniques for Maintaining Shortest Routes in Dynamic Networks, Electronic Notes in Theoretical Computer Science (ENTCS), v.171 n.1, p.3-15, April, 2007
David R. Karger, Minimum cuts in near-linear time, Journal of the ACM (JACM), v.47 n.1, p.46-76, Jan. 2000
Timothy M. Chan, Dynamic subgraph connectivity with geometric applications, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
Jacob Holm , Kristian de Lichtenberg , Mikkel Thorup, Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, Journal of the ACM (JACM), v.48 n.4, p.723-760, July 2001
Mikkel Thorup, Worst-case update times for fully-dynamic all-pairs shortest paths, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
Eran Eyal , Dan Halperin, Dynamic maintenance of molecular surfaces under conformational changes, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
Camil Demetrescu , Giuseppe F. Italiano, Fully dynamic all pairs shortest paths with real edge weights, Journal of Computer and System Sciences, v.72 n.5, p.813-837, August 2006
dynamic graph algorithms;connectivity