View/hide extracted text (may have errors)
Dynamic graph connectivity in polylogarithmic worst case time
Bruce M. Kapron * Valerie King * Ben Mountjoy *
Abstract Though the problem of improving the worst case up-
√
The dynamic graph connectivity problem is the following: date time from O( n) has been posed in the literature
given a graph on a fixed set of n nodes which is undergoing many times, there has been no improvement since 1985.
a sequence of edge insertions and deletions, answer queries
of the form q(a,b): “Is there a path between nodes a and b?” In the words of P˘atra¸scu and Thorup, it is “perhaps
While data structures for this problem with polylogarithmic the most fundamental challenge in dynamic graph algo-
amortized time per operation have been known since the rithms today” [11].
mid-1990’s, these data structures have Θ(n) worst case time.
In fact, no previously known solution has worst case time per Nearly every dynamic connectivity data structure√
operation which is o( n). maintains a spanning forest F. Dealing with edge
We present a solution with worst case times O(log4 n) insertions is relatively easy. The challenge is to find a
per edge insertion, O(log5 n) per edge deletion, and replacement edge when a tree edge is deleted, splitting
O(log n/ log log n) per query. The answer to each query is
a tree into two subtrees. A replacement edge is an edge
correct if the answer is “yes” and is correct with high prob-
ability if the answer is “no”. The data structure is based on reconnecting the two subtrees, or, in other words, in the
a simple novel idea which can be used to quickly identify an cutset of the cut (T,V \T) where T is one of the subtrees.
edge in a cutset.
An edge with both endpoints in the same subtree we call
Our technique can be used to simplify and significantly
internal to the tree.
speed up the preprocessing time for the emergency planning
This paper uses a simple idea for finding replace-
problem while matching previous bounds for an update, and
ment edges: Every replacement edge has exactly one
to approximate the sizes of cutsets of dynamic graphs in time
endpoint in a subtree; all other edges have 0 or 2.
˜(min{|S|, |V \ S|}) for an oblivious adversary.
We exploit this in different ways. For the dynamic
connectivity algorithm, we can add the name of each
1 Introduction
edge to the values stored at both its endpoints, and
The dynamic connectivity problem is as follows: We maintain the bitwise XOR of the values of every node
are given an undirected graph G = (V,E), where V is a in a tree. We observe the bitwise XOR of the names
fixed set of n nodes, and an online sequence of updates of all internal edges in a tree is 0 for internal edges,
and queries, of the following form: but reveals the name of the replacement edge if there
is exactly one of these. Alternatively, we can randomly
• Delete(e): Delete edge e from E.
assign one endpoint of an edge to -1 or 1 and the other
endpoint to the remaining value, then use the sum to
• Insert(e): Insert edge e into E.
approximate the size of the cut. While the basic data
• Query(a,b): Is there a path between nodes a and b? structure used here is simple, designing an algorithm
which preserves sufficient independence of randomness
over the course of many updates presented quite a
The goal is to build a data structure so as to minimize challenge.
the cost per operation. The previously known state
√
of the art for this problem is O( n) worst case up- Main Result: For the dynamic connectivity prob-
date time, due to Frederickson (1985) [5], as improved lem, our data structure is initialized in time
√
from O( m) through use of the sparsification technique O(n log4 n + m log3 n) where n is the number of
of the Eppstein, et.al. [4]. In the 1990’s data struc- nodes and m is the number of edges in the initial graph.
tures with polylogarithmic amortized update time were Each insertion of an edge requires worst case O(log4 n)
developed, but these algorithms have worst case time time; each deletion of an edge requires worst case
˜(n). Each of these algorithms have query time ˜(1). O(log5 n) time. Each query requires O(log n/ log log n)
worst case time. If the answer to a query is “yes,” then
the answer is always correct; if it is “no,” then it is
*Department of Computer Science, University of Victoria, c for c any constant./n1-correct with probability 1
BC, Canada; bmkapron@uvic.ca, val@uvic.ca; mountjoy@uvic.ca.
This research was funded by NSERC We assume the adversary knows the edges in the graph,
1131 Copyright © SIAM.
Unauthorized reproduction of this article is prohibited.
