Parallel Batch-Dynamic Graph Connectivity

In this paper, we study batch parallel algorithms for the dynamic connectivity problem, a fundamental problem that has received considerable attention in the sequential setting. The best sequential algorithm for dynamic connectivity is the elegant level-set algorithm of Holm, de Lichtenberg and Thorup (HDT), which achieves O(1g(2) n) amortized time per edge insertion or deletion, and O(1g n) time per query. We design a parallel batch-dynamic connectivity algorithm that is work-efficient with respect to the HDT algorithm for small batch sizes, and is asymptotically faster when the average batch size is sufficiently large. Given a sequence of batched updates, where A is the average batch size of all deletions, our algorithm achieves O(1g n lg(1 + n/A)) expected amortized work per edge insertion and deletion and O (1g(3) n) depth w.h.p. Our algorithm answers a batch of k connectivity queries in O(k lg(1 + n/ k)) expected work and O(1g n) depth w.h.p. To the best of our knowledge, our algorithm is the first parallel batch-dynamic algorithm for connectivity.