Dynamic Graph Connectivity in Polylogarithmic Worst Case Time

The dynamic graph connectivity problem is the following: given a graph on a fixed set of n nodes, design a data structure to process an online sequence of updates in the form of edge insertions and deletions, and queries of the form q(a,b): "is there a path between nodes a and b?" While data structures for this problem with polylogarithmic *amortized* time per operation have been known since the mid-1990's, these data structures have Theta(n) worst case time. In fact, no previously known solution has worst case time per operation which is o(sqrt n).

In this talk I'll explain a solution with worst case times O(log^4 n) per edge insertion, O(log^5 n) per edge deletion, and O(log n/loglog n) per query. The answer to each query is correct if the answer is "yes" and is correct with high probability if the answer is "no." The data structure is based on a simple novel idea which can be used to quickly identify an edge in a cutset.

This work is joint with Bruce Kapron and Ben Mountjoy.