arXiv:1611.09072v3 [] 28 Feb 2017

Faster Randomized Worst-Case Update Time for Dynamic
Subgraph Connectivity
Ran Duan
Tsinghua University

Le Zhang
Tsinghua University

duanran@mail.tsinghua.edu.cn

le-zhang12@mails.tsinghua.edu.cn

Abstract
Real-world networks are prone to breakdowns. Typically in the underlying graph G, besides
the insertion or deletion of edges, the set of active vertices changes overtime. A vertex might
work actively, or it might fail, and gets isolated temporarily. The active vertices are grouped
as a set S. S is subjected to updates, i.e., a failed vertex restarts, or an active vertex fails,
and gets deleted from S. Dynamic subgraph connectivity answers the queries on connectivity
between any two active vertices in the subgraph of G induced by S. The problem is solved by
a dynamic data structure, which supports the updates and answers the connectivity queries. In
e 2/3 ) deterministic amortized
the general undirected graph, the best results for it include O(m
√
4/5
e
e
update time, O(m ) and O( mn) deterministic worst-case update time. In the paper, we
e 3/4 ) worst-case update time.
propose a randomized data structure, which has O(m

1

Introduction

Dynamic subgraph connectivity is defined as follows: Given an undirected graph G = (V, E) with
|E| = Ω(V ), there is a subset S ⊆ V . E is subjected to edge updates of the forms insert(e, E)
or delete(e, E), where e is an edge. Besides, given v ∈ V , there are vertex updates of the forms
insert(v, S) or remove(v, S). Through vertex updates, S changes overtime. We want to query
whether any two vertices s and t are connected in the subgraph of G induced by S, i.e. a query of
the form connected(s, t, S) for s, t ∈ S.
The problem was first proposed by Frigioni and Italiano [10], where it was referred to as complete
dynamic model, and poly-logarithmic algorithms on connectivity were described for the special case
of planar graphs. As to the general graphs Chan [2] first described an algorithm of deterministic
e 4ω/(3ω+3) )1 , where m is the number of edges, and ω is the matrix multiamortized update time O(m
plication exponent. Adopting FMM (Fast Matrix Multiplication) algorithm of [5], the update time
e 1/3 ) and linear, respectively. Following it,
is O(m0.94 ). Its query time and space complexity are O(m
Chan, Pǎtraşcu, and Roditty [3] proposed a simpler algorithm, having the improved update time
e 2/3 ). The space complexity of the new algorithm increases to O(m
e 4/3 ). The new algorithm
of O(m
is of compact description, getting rid of the use of FMM. With the same update time, Duan [7]
presented new data structures occupying linear space. The worst-case udpate time algorithm is
first considered by Duan [7]. The algorithm proposed has the deterministic worst-case update time
e 4/5 ). Via an application of dynamic DFS tree [1], Baswana et al. proposed a new algorithm
of O(m
1

e hides poly-logarithmic factors.
O(·)

1

e √mn) deterministic worst-case update time. Its query time is O(1). Recently it has an
with O(
improvement [4]. These results are summarized in Table 1.
A close related problem is dynamic graph connectivity, which cares only about the edge updates.
Poly-logarithmic amortized update time was first achieved by Henzinger and King [13]. The algorithm proposed is randomized Las Vegas. Inspired by it, Holm et al. [14] proposed a deterministic
algorithm with O(lg2 n)2 amortized update time, which is now one of the classic results in the
field. A cell-probe lower bound of Ω(lg n) per operation was proved by Pǎtraşcu and Demaine [19].
The lower bound is amortized randomized. Near-optimal results were considered by Thorup [21],
where a randomized Las Vegas algorithm was described with O(lg n(lg lg n)3 ) amortized update
time. The upper bound is recently improved to O(lg n(lg lg n)2 ) by Huang et al. [15]. Besides the
classic deterministic O(lg2 n) result, a faster deterministic algorithm was proposed by Wulff-Nilsen
[23], of which the update time is O(lg2 n/ lg lg n). Turning to the worst-case dynamic connectivity,
√
√
a deterministic O( n) update-time algorithm is Frederickson’s O( m) worst-case algorithm [9]
sped up via sparsification technique proposed by Eppstein et al. [8]. The result holds for online
updating of minimum spanning trees. With roughly the same structure, but different and simpler
techniques,
Kejlberg-Rasmussen et al. [17] provided the so far best deterministic worst-case bound
p
√
of O( n(lg lg n)2 / lg n) for dynamic connectivity. After the discovery of O( n) update-time algorithm, people were wondering whether any poly-logarithmic worst-case update time algorithm
is possible, even randomized. The open problem stands firmly for many years. A breakthrough
should be attributed to Kapron et al. [16]. Their algorithm is Monte-Carlo, with poly-logarithmic
worst-case update time. It has several improvements until now, as done in [11, 22]. For subgraph
e
connectivity, the trivial update time of O(n)
follows from Kapron et al.’s algorithm. The query
time of it for subgraph connectivity can also be improved to O(1), as the explicit maintenance of
e
connected components can be done without blowing up the O(n)
update time.

1.1

Our Results

e 4/5 ) deterministic worst-case subgraph connectivity structure adopted as a subThe former O(m
√
routine the O( n) deterministic worst-case algorithm for dynamic graph connectivity. Now the
randomized poly-logarithmic worst-case connectivity structures for dynamic graph connectivity are
discovered. We consider the question of whether it brings progress in subgraph connectivity. The
√
answer is affirmative. However, it does not come by replacing the O( n) deterministic algorithm
e 4/5 )
with the poly-logarithmic randomized one. Carefully tuning the former setting of the O(m
2/3
e
algorithm is also in vain. Intuitively, the amortized O(m ) update time was achieved partially
because it uses the connectivity structure of poly-logarithmic amortized update time. Now polye 2/3 ) worst-case update time
logarithmic worst-case algorithms are discovered, it seems that the O(m
e
is in sight. Nonetheless, we found that it is still hard to get the O(m2/3 ) update time. Until now we
e 3/4 ). Although it only improves the previous deterministic O(m
e 4/5 )
obtain the update time of O(m
e 2/3 ) and O(m
e 4/5 ) is
bound by m0.05 , note that the gap between the two deterministic results O(m
0.134
only m
. The main contribution is a new organization of the auxiliary data structures.
√
e
The O( mn) result comes from dynamic DFS tree [1, 4], which is a periodic rebuilding technique
e 3/4 ) update time of our result is always no worse
with fault tolerant DFS trees. Note that the O(m
√
1/2
e mn) as n = Ω(m ).
than O(
Faster query time can be traded with slower update time for the bottom four results in Table
e 3/4+ ) update time and O(m
e 1/4− ) query time can be implemented. The
1. As to our result, O(m
2

We use lg x to denote log2 x.

2

Table 1: Results on Dynamic Subgraph Connectivity
Update time Query time
Notes
Amortized,
e 4ω/(3ω+3) )
e 1/3 )
O(m
O(m
deterministic, linear space [2]
√
Worst case,
e mn)
O(
O(1)
e
deterministic, space O(m)
[1, 4]
Amortized,
e 2/3 )
e 1/3 )
O(m
O(m
e 4/3 ) [3]
deterministic, space O(m
Amortized,
e 2/3 )
e 1/3 )
O(m
O(m
deterministic, linear space [7]
Worst case,
e 4/5 )
e 1/5 )
O(m
O(m
e
deterministic, space O(m)
[7]
Worst
case,
e 3/4 )
e 1/4 )
O(m
O(m
randomized, linear space, this paper
details concerning these trade-offs are interpreted in Appendix D. Note that the trade-offs are in
one direction, i.e. better query time with worse update time, but not vice-versa. Consequently,
e 4/5 ) algorithm never gives update time of O(m
e 3/4 ). The trade-off phenomenon is
the former O(m
definitely hard to break, as indicated by the OMv (Online Boolean Matrix-Vector Multiplication)
conjecture proposed by Henzinger et al. [12]. The OMv conjecture rules out polynomial preprocessing time algorithms with the product of amortized update and query time being o(m).
Finally, our result is grouped as the following theorem.
Theorem 1.1 (Main Theorem). Given a graph G = (V, E), there is a data structure for the
e 3/4 ), query
dynamic subgraph connectivity, which has the worst-case vertex (edge) update time O(m
1/4
e
time O(m
), where m is the number of edges in G, rather than in the subgraph of G induced by
S. The answer to each query is correct if the answer is “yes”, and is correct w.h.p. if the answer
e 5/4 ), and the space usage is linear.
is “no.” The pre-processing time is O(m

2

Preliminaries

We review the two results on dynamic graph connectivity, which are adopted as sub-routines in our
data structure. The first one is deterministic, and the second one is randomized. Given G = (V, E)
with n vertices and m edges, the properties of the two data structures are described in the following
two theorems.
Theorem 2.1 ([17]). A p
spanning forest F of G can be maintained by a deterministic data structure
of linear space, with O( m(lg lg n)2 /lg n) worst-case update time for an edge update in G, and
constant query time to determine whether two vertices are connected in G.
Theorem 2.2 ([16]). There is a randomized data structure on dynamic graph connectivity, which
supports the worst-cast time O(lg4 n) per edge insertion, O(lg5 n) per edge deletion, and O(lg n/ lg lg n)
per query. For any constant c the answer to each query is correct if the answer is “yes” and is correct
with probability ≥ 1−1/nc if the answer is “no.” The pre-processing time of it is O(m lg3 n+n lg4 n).

3

For dynamic subgraph connectivity, we first consider the case when the updates are only vertex
updates. The extension to edge updates is deferred to Appendix C. Hence temporarily G is assumed
to be static, as E does not change if there are no edge updates. The vertex updates change S.
Initially, G is slightly modified to keep m = Ω(n) during its lifetime, i.e., for every v ∈ V , insert
a new vertex v 0 and a new edge (v, v 0 ). The variant graph has m = Ω(n), which is required in
the definition of the dynamic subgraph connectivity [2]. It facilitates the presentation of time and
space complexity as functions of m, rather than of n in the case of degenerate graphs.

3

The Data Structure

We give some high-level ideas. Main difficulties are the update of S (recall that S is the set of active
vertices) incurred by the high-degree vertices, as their degrees are too high to explicitly delete their
incident edges one by one. Nonetheless, if the low-degree vertices had been removed, the graph
became smaller, and consequently former high-degree vertices were not high-degree anymore. Hence
our aim is to remove the low-degree vertices. After that, some artificial edges are added to restore
the loss of connectivity due to the removal of the low-degree vertices. Next a dynamic connectivity
data structure is maintained on the modified graph, i.e., the graph with the low-degree vertices
removed, and the artificial edges added. Besides, as S evolves dynamically, we need to update the
artificial edges accordingly. Hence the point is how to maintain these artificial edges consistently
and efficiently. We now move to the details. We partition V according to their degrees in G. Use
degG (v) to denote the degree of v in G.
• C : Vertices with degG (v) > m1/2
• B: Vertices with m1/4 < degG (v) ≤ m1/2
• A: Vertices with degG (v) ≤ m1/4
Denote C ∩ S, B ∩ S, and A ∩ S as VC , VB , and VA respectively. Consider the subgraph GA of G
induced by VA . Define the degree of a component as the sum of degG (v)’s for v’s in it. According
to the degrees of the components, partition the components of GA into two types: high component,
with its degree > m1/4 ; low component, with its degree ≤ m1/4 . A spanning forest FA of GA is
maintained by the deterministic connectivity structure of Theorem 2.1.

3.1

Path Graph

A path graph inserts some artificial edges to reflect the “are connected” relation of the vertices
within VB via directly linking with a component of GA . The idea was proposed in [7], whereas here
we describe it more rigorously, giving more details. W.l.o.g. assume V = {0, . . . , n − 1}. Consider
a spanning tree T of FA .
• subpath tree: For v ∈ T , identify the set of vertices in VB that are adjacent to v. Store the
set of vertices in a balanced search tree, which has the worst-case O(lg n) update time for the
well-known search-tree operations [6]. Name the search tree as the subpath tree of v. Given
the subpath tree of v, a sequence of artificial edges is added to link the vertices stored in the
subpath tree of v. The sequence of artificial edges constitutes a subpath.

4

15
Part of VB 3

11

4

10

2

7
6

14
ET-order

T in GA

h1, 5, 8, 13, 12, 9i

9
1

12

5
8

13

h1, 12, 9i
h2, 15i h3, 15i
h4, 10, 14i

Figure 1: The path graph of VB w.r.t. a spanning tree T in FA . The dashed edges represent edges
between VB and VA . The path tree is on sequence h1, 12, 9i, and three subpath trees are on sequences
h2, 15i, h4, 10, 14i, and h3, 15i respectively. The resulted path graph is a path h2, 15, 4, 10, 14, 3, 15i.
• path tree: Given T ∈ FA , group all v ∈ T with the non-empty subpath tree as a balanced
search tree, ordered by the Euler-tour order of T (See Appendix A.). Name it as the path tree
of T . As each vertex stored in the path tree of T has an associated subpath, these subgraphs
are also concatenated one by one via the artificial edges, generating a path. To emphasize
its difference from an ordinary path, it is referred to as the path graph of VB w.r.t. T . An
example is shown in Fig. 1.
e 1/2 ) time for a vertex update in VB , and in
Lemma 3.1. The path graphs can be updated in O(m
e
O(1)
time for a link or cut on FA .
Proof. We categorize the analysis into two cases.
• Reflect a vertex update in VB : Suppose v ∈ VB is removed from S. The case of insertion is
similar. v has ≤ m1/2 edges adjacent to FA . Consider (v, w) with w ∈ T . We locate w in the
path tree of T . Now the subpath associated with w is known. Update the subpath of w by
removing v from the subpath. If v happens to be the first or the last vertex on the subpath,
the path graph of T is also updated. As the subpaths and the path graph are concerned with
the nodes stored in the subpath trees and the path tree respectively, which are all balanced
e
search trees, the removal of (v, w) needs O(1)
time. The removal of all such (v, w)’s requires
1/2
e
O(m
) time.
• Reflect a link or cut on FA : We only discuss the edge cut on FA . The edge link is similar.
Assume the edge cut is (v, w) ∈ T , and the Euler tour of T is hL1 , (v, w), L2 , (w, v), L3 i (The
details on Euler tours can be found in Appendix A.). After the cut of (v, w), the Euler tours
for the two resulted trees are hL1 , L3 i and hL2 i. We can determine the first vertex a and
the last vertex b of hL2 i. With the order tree of T presented in Appendix A, the predecessor
of a and the successor of b in the path tree of T can be found in O(lg2 n) time. With the
predecessor and the successor, the path tree of T is split. After the split, O(1) edges in the
path graph are removed to reflect the split of the path tree of T . As a conclusion, the path
e
graph can be updated in O(1)
time to reflect a link or cut on FA .

5

3.2

Adjacency Structure

Given T ∈ FA and v ∈ C, we want a data structure that provides the fast query of whether T and
v are adjacent, i.e., whether an edge (u, v) exists with u ∈ T . The adjacency structure presented
in [7] can answer such queries. Here we describe it more rigorously, giving more details. Assuming
v ∈ C, the adjacency structure of v contains the following search trees.
• sub-adjacency tree: Given T ∈ FA , identify the set of vertices in T that are adjacent to v.
Store the set of vertices as a balanced search tree, ordered by the Euler-tour order of T (See
Appendix A.). Name the balanced search tree as the sub-adjacency tree of v w.r.t. T .
• adjacency tree: Identify T ∈ FA by the smallest vertex in T . Group all T ∈ FA , w.r.t. which
v has non-empty sub-adjacency trees, as a balanced search tree. Name the balanced search
tree as the adjacency tree of v.
The sub-adjacency trees and the adjacency tree of v constitute the adjacency structure of v
w.r.t. FA . The query aforementioned is answered by checking whether T is in the adjacency tree of
v. Note v ∈ C, rather than ∈ VC . The adjacency structure of v ∈ C w.r.t. FA is maintained even
if v ∈
/ S.
e 1/2 ) time for a link
Lemma 3.2. The adjacency structures of C w.r.t. FA can be renewed in O(m
e
or cut on FA . Given a query of whether v ∈ C is adjacent to T ∈ FA , it can be answered in O(1)
time.
Proof. We only discuss the edge cut on FA . The edge link is similar. The adjacency structures of
the vertices in C are renewed one by one. Consider v ∈ C. Suppose the edge cut occurs on T ,
splitting T into T1 and T2 . We check whether T is in the adjacency tree of v. If “no”, the update is
done; if “yes”, remove T from it, and update the sub-adjacent tree of v w.r.t. T to reflect the edge
cut on T . For Tj (j = 1, 2), add Tj into the adjacent tree of v if it is adjacent to v (determined
by whether a sub-adjacent tree of v exists w.r.t. Tj ). For every vertex in C, we need to check and
e 1/2 ), since |C| is O(m1/2 ).
update when necessary. Hence the total update time is O(m

3.3

The Whole Structure

Now we turn to the discussion of the whole structure of our result. First, VA is removed. After
that some artificial vertices and edges are added to the subgraph of G induced by VB ∪ C, resulting
in a graph H. (Note that we include the vertices in C \ S, rather than just VC , which is C ∩ S.)
The artificial vertices and edges are used to restore the loss of connectivity due to the removal of
VA . Recall that the components of GA are either low or high. We describe how the artificial edges
or vertices are added as follows.
• Added by the path graphs: For T ∈ FA , construct the path graph of VB w.r.t. T .
• Added by the high components: For a high component P ∈ GA , add a meta-vertex. For
v ∈ C adjacent to P , add an artificial edge between v and the meta-vertex. Identify the first
vertex of the path graph of VB w.r.t. T , where T is the spanning tree of P . Add an artificial
edge between the first vertex and the meta-vertex.

6

C

VB

VA

Figure 2: An example of the whole structure. The irrelevant edges within VA , VB , and C are
omitted for clarity. The solid edges are the edges in G, while the dotted edges denote the artificial
edges. The grey vertex in the VB layer indicates a meta-vertex. The left component of VA is low;
whereas the right one is high. We construct a complete graph within the vertices in C w.r.t. the
low component.
• Added by the low components: For a low component Q ∈ GA , construct a complete graph
within the vertices in C that are adjacent to Q. Similarly as above, identify the first vertex
of the path graph of VB w.r.t. T , where T is the spanning tree of Q. Add the artificial edges
between the first vertex and the vertices in C that are adjacent to Q.
After these, H can be defined as follows.
• The vertex set V (H) of H: VB ∪ C ∪ M , where M is the set of meta-vertices. Since the
degree of a high component is > m1/4 , and the vertices in VB ∪ C are of degree > m1/4 , H
has O(m3/4 ) vertices.
• The edge set E(H) of H: The original edges of G within VB ∪ C, and the artificial edges.
Figure 2 gives an example for the construction. H is a multigraph. Use D[u, v] > 0 of edge
multiplicity to represent the edge (u, v) ∈ E(H). The discussion on the maintenance of D[u, v]’s is
deferred to the end of the subsection. Now we construct a graph G∗ , based on H.
• The vertex set V (G∗ ) of G∗ : VB ∪ VC ∪ M .
• The edge set E(G∗ ) of G∗ : The edges (u, v)’s with D[u, v] > 0, where u, v ∈ V (G∗ ), u 6= v.
G∗ is a variant of the subgraph of H induced by VB ∪ VC ∪ M . It excludes the vertices in C \ S,
i.e., only the vertices in VC of C are contained. Besides, the multiple edges are substituted by
the single ones. G∗ is a simple graph. The randomized connectivity structure of Theorem 2.2 is
maintained on G∗ .
About the D[u, v]’s aforementioned, a balanced search tree is used to store them, with D[u, v]
indexed by u + nv (assuming u ≤ v). Only D[u, v] > 0 is stored in the search tree. We can check
whether D[u, v] is in the search tree in O(lg n) time. Along the process of the updates, we might
increment or decrement D[u, v]’s. When D[u, v] decrements to 0, we remove it from the search tree.
If both u and v are the vertices in G∗ and u 6= v, the edge (u, v) is deleted from G∗ . Similarly,
7

when D[u, v] increments to 1, we add it to the search tree. If both are the vertices in G∗ and u 6= v,
the edge (u, v) is inserted into G∗ . G∗ captures the property of connectivity, which is stated in the
following lemma.
Lemma 3.3. For any two vertices u, v ∈ VB ∪ VC , they are connected in the subgraph of G induced
by S if and only if they are connected in G∗ .
Proof. G∗ is a variant of the subgraph of G induced by S. G∗ removes VA from the subgraph.
Connectivity within VB via VA is restored by the path graphs. Connectivity within VC via VA
is restored either by linking with the same meta-vertex, or by the complete graph constructed.
Lastly, for the connectivity between VC and VB via VA , it is restored by the first vertex of the
path graph linking with the meta-vertex, or with all the relevant vertices in VC . Consider a path
between u and v in the subgraph induced by S, the segments of the path consisting only of the
vertices in VA can be eliminated, as the “via VA ” connectivity is restored as discussed. The lemma
follows.

3.4

Update and Query

We discuss how the vertex updates are reflected efficiently in the whole structure constructed. The
difficulty is to keep D[u, v]’s being consistent with S. As E(G∗ ) is a subset of the (u, v)’s with
D[u, v] > 0, it might also need to be updated. We present the query algorithm and analyze it at
the end of the subsection.
e 3/4 ).
Lemma 3.4. The whole structure constructed has the worst-case vertex update time O(m
Proof. We discuss the various cases of vertex updates, categorized according to whether v ∈ A, or
∈ B, or ∈ C.
• v ∈ A: Consider the case of inserting v into S. v is first inserted as a singleton component
containing only v in GA . Next the edges incident on v are restored in the following order:
First, the edges between v and C; second, the edges between v and VB ; third, the edges
between v and VA .
Restore the edges between v and C: For every u adjacent to v where u ∈ C, construct a
sub-adjacency tree (containing only v) of u, and insert v into the adjacency tree of u. Next
the complete graph within these u’s in C is constructed. Because degG (v) ≤ m1/4 , i.e. a low
e 1/2 ), dominated by constructing the complete graph.
component, the update time is O(m
Restore the edges between v and VB : Construct the subpath tree and the path tree of v. Add
the path-graph edges associated with v (Add means incrementing the corresponding entry
D[u, v]), and the edges between the first vertex of the path graph and the vertices in C that
e 1/4 ).
are adjacent to v. The update time is O(m
e √m) deterministic data structure maintaining FA
Restore the edges between v and VA : O(
e 3/4 ) time. As degG (v) ≤ m1/4 , the link or cut on FA happens O(m1/4 )
is updated in O(m
e 1/4 ) time.
times. Consequently, according to Lemma 3.1, the path graphs are updated in O(m
e 3/4 ) time.
According to Lemma 3.2, the adjacency structures are updated in O(m
O(m1/4 ) components of GA are affected. For every high component, using the adjacency
structures, the edges between C and the meta-vertex (corresponding to the high component)
8

e 1/2 ) time according to Lemma 3.2, since |C| = O(m1/2 ); for every
can be determined in O(m
e 1/2 ) time suffices to conlow component, as the degree of a low component is ≤ m1/4 , O(m
struct the complete graph within the vertices in C that are adjacent to the low component,
e 1/4 ) time suffices to construct the edges between the first vertex of the path graph
and O(m
w.r.t. the low component and the vertices in C that are adjacent to the low component.
e 1/2 ). The
Hence no matter whether the component is low or high, the update time is O(m
e 3/4 ). Deleting of v ∈ S from S is a reverse
time needed to update all these components is O(m
e 3/4 ) time.
process. In summary, a vertex update of v ∈ A requires O(m
• v ∈ B: Consider the case when v ∈ S is removed. The case of insertion is the reverse.
First destroy the edges between v and VA . According to Lemma 3.1, the path graphs can
e 1/2 ) time. Besides, v might be the first vertex of some path graphs. We
be updated in O(m
see how it is updated. v can be adjacent to ≤ m1/2 components of GA , as degG (v) ≤ m1/2 .
For a high component, as only one edge linking v with the meta-vertex, the update is easy;
e 1/4 )
for a low component, since only ≤ m1/4 edges can be outward for a low component, O(m
time suffices for updating the edges between v and the vertices in C that are adjacent to the
low component. Hence the update time for v being the first vertex of some path graphs is
e 3/4 ). Until now the artificial edges concerning v are removed. Other edges concerning v
O(m
e 1/2 )
are the original edges in G. Hence we can remove these original edges one by one in O(m
1/2
3/4
e
).
time as degG (v) ≤ m . In summary, the total update time of v ∈ B is O(m
e 3/4 ). The relevant
• v ∈ C: As there are only O(m3/4 ) vertices in G∗ , the update time is O(m
D[u, v]’s are left intact, and the adjacency structure of v is not destroyed (if v is removed
e 3/4 ).
from S). The total update time is O(m

Now we describe the query algorithm: Given u, v ∈ S, the goal is to substitute them with the
equivalent vertices in G∗ , where an equivalent vertex of u (or v) is a vertex in G∗ that is connected
with u (or v). As V (G∗ ) = VB ∪ VC ∪ M , if u, v ∈ VB ∪ VC , the search for the equivalent vertices
is done. Otherwise, if u (or v) is in a high component, replace u (or v) with the meta-vertex
corresponding to the high component; if u (or v) is in a low component, exhaustively search the
outward edges of the low component for a vertex of G∗ . When the equivalent vertex of u (or v)
cannot be found, it indicates that u (or v) is in a low component of GA , and the low component is
not connected with any vertex in VB ∪ VC . Intuitively u (or v) is on an “island” of GA .
e 1/4 ). The answer to every query
Lemma 3.5. The time complexity of the query algorithm is O(m
is correct if the answer is “yes”, and is correct w.h.p. if the answer is “no”.
Proof. Connectivity within G∗ is answered by the randomized connectivity structure on G∗ ; whereas
for the other cases, u and v are connected if and only if they are in the same component of GA ,
of which the queries can be answered by the deterministic connectivity structure on GA . The time
complexity is dominated by the exhaustive search if u (or v) is in a low component, and thus is
e 1/4 ).
O(m
The correctness can be analyzed as follows. If u, v ∈ VB ∪ VC , it follows from Lemma 3.3;
otherwise, for any one not in, we only replace it with an equivalent vertex of G∗ . If such an
equivalent vertex cannot be found, the queried vertex is on an island aforementioned of GA . Then
u and v are connected if and only if they are on the same island. We analyze the error probability. A
9

deterministic connectivity structure is adopted for GA . FA is always a spanning forest of GA . The
queries are answered either by the deterministic connectivity structure if at least one queried vertex
is on an island aforementioned of GA , or by the randomized connectivity structure if both queried
vertices are (replaced with) the vertices in G∗ . The deterministic connectivity structure always
gives the right answer; whereas the randomized one might answer erroneously. The randomized
algorithm of [16] maintains a private witness of a spanning forest of G∗ . The algorithm has the
property that after every update, the witness is a spanning forest of G∗ with probability ≥ 1−1/nc .
It is the property which ensures the answers are correct w.h.p.. Here, after every vertex update
(which is transformed into a sequence of edge updates in G∗ ), the witness for G∗ is also a spanning
forest of G∗ w.h.p. after the vertex update. We can just focus on the correctness of the witness at
the point after the last transformed edge update. Consequently, the error probability is negligible,
i.e., ≤ 1/nc for any constant c.
The analysis of space and pre-processing time is presented in Appendix B. The main theorem,
i.e. Theorem 1.1, follows from Lemmas 3.4, 3.5, B.1, and C.1.

References
[1] Surender Baswana, Shreejit Ray Chaudhury, Keerti Choudhary, and Shahbaz Khan. Dynamic
DFS in undirected graphs: breaking the O(m) barrier. In Proceedings of the twenty-seventh
Annual ACM-SIAM Symposium on Discrete Algorithms, pages 730–739. SIAM, 2016.
[2] Timothy M. Chan. Dynamic subgraph connectivity with geometric applications. In Proceedings
of the thiry-fourth annual ACM Symposium on Theory of Computing, pages 7–13. ACM, 2002.
[3] Timothy M. Chan, Mihai Pǎtraşcu, and Liam Roditty. Dynamic connectivity: Connecting to
networks and geometry. SIAM Journal on Computing, 40(2):333–349, 2011.
[4] Lijie Chen, Ran Duan, Ruosong Wang, and Hanrui Zhang. Improved algorithms for maintaining DFS tree in undirected graphs. CoRR, abs/1607.04913, 2016.
[5] Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions.
Journal of Symbolic Computation, 9(3):251 – 280, 1990. Computational algebraic complexity
editorial.
[6] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction
to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009.
[7] Ran Duan. New data structures for subgraph connectivity. In Automata, Languages and
Programming, pages 201–212. Springer, 2010.
[8] David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig. Sparsification–a
technique for speeding up dynamic graph algorithms. Journal of the ACM, 44(5):669–696,
1997.
[9] Greg N. Frederickson. Data structures for on-line updating of minimum spanning trees, with
applications. SIAM Journal on Computing, 14(4):781–798, 1985.

10

[10] Daniele Frigioni and Giuseppe F. Italiano. Dynamically switching vertices in planar graphs.
Algorithmica, 28(1):76–103, 2000.
[11] David Gibb, Bruce M. Kapron, Valerie King, and Nolan Thorn. Dynamic graph connectivity
with improved worst case update time and sublinear space. CoRR, abs/1509.06464, 2015.
[12] Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak.
Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proceedings of the forty-seventh Annual ACM on Symposium on
Theory of Computing, pages 21–30. ACM, 2015.
[13] Monika R. Henzinger and Valerie King. Randomized fully dynamic graph algorithms with
polylogarithmic time per operation. Journal of the ACM, 46(4):502–516, 1999.
[14] Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic
fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity.
Journal of the ACM, 48(4):723–760, 2001.
[15] Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, and Seth Pettie. Fully dynamic connectivity
in O(log n(log log n)2 ) amortized expected time. In Proceedings of the twenty-eighth Annual
ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2017.
[16] Bruce M. Kapron, Valerie King, and Ben Mountjoy. Dynamic graph connectivity in polylogarithmic worst case time. In Proceedings of the twenty-fourth Annual ACM-SIAM Symposium
on Discrete Algorithms, pages 1131–1142. SIAM, 2013.
[17] Casper Kejlberg-Rasmussen, Tsvi Kopelowitz, Seth Pettie, and Mikkel Thorup. Faster worst
case deterministic dynamic connectivity. In Proceedings of the twenty-fourth Annual European
Symposium on Algorithms, 2016.
[18] Peter Bro Miltersen, Sairam Subramanian, Jeffrey Scott Vitter, and Roberto Tamassia. Complexity models for incremental computation. Theoretical Computer Science, 130(1):203–236,
1994.
[19] Mihai Pǎtraşcu and Erik D. Demaine. Logarithmic lower bounds in the cell-probe model.
SIAM Journal on Computing, 35(4):932–963, 2006. Special issue of selected papers from the
thirty-sixth ACM Symposium on Theory of Computing, 2004.
[20] Robert E. Tarjan. Dynamic trees as search trees via Euler tours, applied to the network
simplex algorithm. Mathematical Programming, 78(2):169–177, 1997.
[21] Mikkel Thorup. Near-optimal fully-dynamic graph connectivity. In Proceedings of the thirtysecond annual ACM Symposium on Theory of Computing, pages 343–350. ACM, 2000.
[22] Zhengyu Wang. An improved randomized data structure for dynamic graph connectivity.
CoRR, abs/1510.04590, 2015.
[23] Christian Wulff-Nilsen. Faster deterministic fully-dynamic graph connectivity. In Proceedings
of the twenty-fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1757–1769.
SIAM, 2013.

11

A

Trees as Euler Tours

An Euler tour (cycle) for a digraph is a cycle that traverses each edge exactly once, although it
may visit a vertex more than once. For a strongly connected digraph, it has an Euler tour if and
only if the in-degree and the out-degree are equal for each vertex. We adopt the Euler tours to
represent the dynamic trees. The representation was first proposed by Miltersen et al. [18] and
independently by Henzinger and King [13].
Given a tree T , following the idea of Tarjan’s [20], we replace each edge {v, w} by two directed
arcs (v, w) and (w, v), and add a self-loop (v, v) for each node v. The resulted digraph always has
at least one Euler tour. Choose any one, and break it at an arbitrary place. Store the resulted list
of directed arcs as a balanced search tree, which is called the Euler-tour tree, a.k.a. ET-tree.
The self-loop (v, v) in the ET-tree actually represents v ∈ T . We can extract the order of these
self-loops, and represent the order in another balanced search tree. Name it the order tree, which
generates an Euler-tour ordering of the nodes of T . We have the following observation.
Observation A.1. Given u, v ∈ T , the order of them w.r.t. the Euler-tour order can be determined
by the order tree in O(lg n) worst-case time.
As shown in [20], the ET-tree of T has O(lg n) worst-case update time for a link or cut operation
on T . We show briefly how to get the order trees for the two resulted trees after an edge cut. The
edge link is similar. Suppose cut({v, w}), and the Euler tour of T is hL1 , (v, w), L2 , (w, v), L3 i. The
Euler tours of the two resulted trees should be hL1 , L3 i and hL2 i. Augment the ET-tree to enable
us to find the first and the last self-loop edges in O(lg n) time. (It is achieved by a boolean bit at
each node of the ET-tree indicating whether there exists a self-loop in the subtree rooted at the
search tree node.) We query the ET-tree of hL2 i to get the first node a and the last node b. The
order trees for the two resulted subtrees can be obtained by splitting the initial order tree first
before a and then after b, and joining the first part and the last part. The update time is easily
observed as follows.
Observation A.2. ET-trees and order trees can be updated in O(lg n) worst-case time for a link or
cut on dynamic trees.

B

Space Complexity and Pre-processing Time

The space usage consists of the deterministic connectivity structure on GA , the search tree storing
D[u, v] > 0, the randomized connectivity structure on G∗ , and the auxiliary structures, e.g., the
adjacency structures. The space complexity and pre-processing time are summarized as the following lemma. From the proof we observe that the pre-processing time is dominated by D[u, v] entries
constructed for the complete-graph edges within C.
Lemma B.1. The pre-processing time of the dynamic subgraph connectivity data structure is
e 5/4 ), and its space usage is linear.
O(m
Proof. We analyze the space complexity and the pre-processing time one by one.
• Space complexity

The deterministic connectivity structure on GA occupies the space proportional to the size
of GA . As the edges in GA are all the original edges in G, it uses linear space.

12

For the D[u, v]’s, the entries corresponding to the original edges in G conform to the goal
of linear-space usage. As to the artificial edges introduced by the path graphs, note that
every original edge in G between a vertex of VB and a vertex of VA is replaced by at most
two edges within the path graphs. For the artificial edges connecting the first vertex of a
path graph with some vertices of C, each one of them is brought because there is an original
edge linking a vertex of C with a low component in GA . The edges between the vertices
of C and the meta-vertices can be accounted for in the same way. Until now every original
edge in G is attributed O(1) times. Hence the space usage excluding the complete graphs
constructed is linear. Considering the excluded edges constructed for the complete graphs,
as only multiplicities are recorded, and |C| = O(m1/2 ), O(m) space suffices. In summary,
D[u, v]’s size is linear.
For the randomized connectivity structure on G∗ , its space usage is O(m0 + n0 lg3 n0 ), for a
graph with m0 edges, n0 vertices. (The lg3 n0 factor is due to O(lg n0 ) cutset data structures,
which are represented by ET-trees maintaining O(lg2 n0 ) values. See [16] for the details.) The
edge set of G∗ is a subset of D[u, v]’s, therefore its cardinality is O(m). As to n0 , its value
for G∗ is O(m3/4 ). In summary, the space usage of the randomized connectivity structure is
linear.
For the other auxiliary data structures, e.g., the adjacency structures, every appearance of
a vertex of VA in a sub-adjacency tree corresponds to an original edge in G between C and
VA . Thus it is linear. In summary, combining all of these, we can see that the total space
complexity is linear.
• Pre-processing time

As to the pre-processing time, the deterministic and randomized connectivity structures both
e
need O(m)
time. Similar to the space usage, excluding the complete graphs, every edge
e
between VA and VB ∪ C induces O(1) artificial edges, and O(1)
pre-processing time suffices.

For the complete graphs, since for every edge from a vertex of C to a low component, O(m1/4 )
edges are added in the complete graphs (the degree of a low component is ≤ m1/4 ). Hence
e 5/4 ). The total pre-processing time is
the pre-processing time for the complete graphs is O(m
e 5/4 ).
dominated by the complete-graph constructions, and thus is O(m

C

Extension to Edge Updates

The structure described in Sect. 3 can be extended to handle the edge updates. As mentioned in
Sect. 2, the data structure is constructed on a variant of G, which has m = Ω(n).
To insert an edge (u, v), the simple trick of creating a new vertex z adjacent to only u and v,
and then inserting z would not work here [2, 3]. The point is that it might violate the type of u
(or v), i.e., which set (A, B or C) it belongs to. On the same time, it also might violate the type
of a component of GA , i.e., whether the component is low or high. Instead, we adopt the following
algorithm for the edge updates.
Step 1 Delete u and v from S, if u or v is ∈ S.
Step 2 Update E.
13

Step 3 Change the type(s) of u (and v). The type transition between C and B is the only case
requiring the extra processing. For the other cases, just mark the new type(s), e.g., if a
former A vertex v becomes a B type, just mark the type of v as B. W.l.o.g., suppose
the degree of a former B vertex u increases to > m1/2 , i.e. a new C vertex. Note that
degG (u) is just Θ(m1/2 ), as it is just above the threshold. We take two steps to deal with
e 1/2 )
them: First, construct its adjacency structure, which can be accomplished in O(m
time; second, insert D[u, v] entries into its search tree. As degG (u) is Θ(m1/2 ), the worst
e 3/4 ) time suffices for
case is that it is adjacent to Θ(m1/2 ) distinct low components. O(m
calculating D[u, v]’s.
Step 4 Insert u and v back into S, if u or v is in ∈ S before the edge update.
The edge-update time is analyzed as follows.
Lemma C.1. The data structure for the dynamic subgraph connectivity has the worst-case edgee 3/4 ), where m is the number of edges in G, i.e. |E|, at the time of the edge-update
update time O(m
operation.
e 3/4 ), as Step 3 only needs O(m
e 3/4 ) time, and
Proof. One can easily see that the update time is O(m
the number of vertex updates is constant. Now we take a look at the value of m.
As m is used as a parameter for the division of vertices and the partition of components, m
should not deviate from the true number of edges m0 currently in graph G by too much. So when
detecting |m0 − m| first ≥ 21 m1/2 , we make a copy G0 of the current graph G, and partition the
0 )5/4 )
e
vertices based on the value of m0 . During the next 41 m1/2 updates, we pre-process G0 in O((m
e 5/4 ) as m0 = Θ(m). The pre-processing is done in the background, and is evenly
time, which is O(m
distributed over the 14 m1/2 updates. After the pre-processing, we start the catching-up process of
performing 21 m1/2 updates during the next followed 41 m1/2 updates of G. By the end of 12 m1/2
updates of G, we replace G with G0 .
e 3/4 ) worst-case update time
For the past 12 m1/2 updates (supported by G), each only spends O(m
e 3/4 ).
on the pre-processing and the catching-up of G0 . So the worst-case update time is still O(m
The crucial point is that for all the past updates, using m is just fine, as the difference between m
and the true value is ≤ m1/2 , i.e., asymptotically these two values are the same.
Now we replace G with G0 . Suppose the current number of edges is m00 . We face a similar
circumstance of |m00 − m0 | ≤ 21 (m0 )1/2 to the former G. Just begin the process above again, if at
some point detecting |m00 − m0 | first ≥ 21 (m0 )1/2 .

D

e 3/4+ ) Update and O(m
e 1/4− ) Query Time
Extension to O(m

e 1/4− ). As before,
We discuss how to adjust the parameters to achieve the query time of O(m
partition the vertices according to the degrees.
• C: Vertices with degG (v) > m1−b
• B: Vertices with m1−a < degG (v) ≤ m1−b
• A: Vertices with degG (v) ≤ m1−a
14

A component of GA is high if its degree is > m1−c ; otherwise, it is low. As a low component can
e 1−c ). Consequently, we can anticipate
be of degree as high as m1−c , the query time should be O(m
c
e
the update time of O(m ). To achieve the desired update time, the following inequalities should
be satisfied.
• Update in A:
(1) Maintaining a spanning forest of GA :

√
m · m1−a ≤ mc .

(2) Maintaining the complete graphs w.r.t. the low components: m1−a · m2(1−c) ≤ mc .

(3) Maintaining the edges between C and the meta-vertices: m1−a · mb ≤ mc .
• Update of a B vertex v:
(4) v can be adjacent to ≤ m1−b low components of GA : m1−b · m1−c ≤ mc .
• Update in C:
(5) The number of vertices in G∗ should be bounded: ma ≤ mc .

From (2) and (5), we have 3 ≤ a + 3c ≤ 4c. It gives the reason why the data structure achieves
e 3/4 ), as c should be ≥ 3/4. Nevertheless, it also tells us c could
the update time no better than O(m
be 3/4 + . By setting b to be 1/2 and a to be 3/4, all inequalities are again satisfied. Hence we
e 3/4+ ) update time and O(m
e 1/4− ) query time.
have a new data structure with O(m

15

