Parallel Batch-Dynamic Graph Connectivity

Abstract

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 most well known sequential algorithm for dynamic connectivity is the elegant level-set algorithm of Holm, de Lichtenberg and Thorup (HDT), which achieves $O({\log }^{2}n)$ amortized time per edge insertion or deletion, and $O(\log n/\log \log 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 $\Delta$ is the average batch size of all deletions, our algorithm achieves $O(\log n\log (1+n/\Delta ))$ expected amortized work per edge insertion and deletion and $O({\log }^{3}n)$ depth w.h.p. Our algorithm answers a batch of $k$ connectivity queries in $O(k\log (1+n/k))$ expected work and $O(\log n)$ depth w.h.p. To the best of our knowledge, our algorithm is the first parallel batch-dynamic algorithm for connectivity.

This is the full version of the paper appearing in the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2019

References in corpus (9)

• Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable
• Parallel Ordered Sets Using Join
• Parallel Batch-Dynamic Graph Connectivity
• PAM: Parallel Augmented Maps
• Parallel Graph Connectivity in Log Diameter Rounds
• Faster Worst Case Deterministic Dynamic Connectivity
• Fully Dynamic Connectivity in $O(\log n(\log \log n{)}^2)$ Amortized Expected Time
• Near Optimal Parallel Algorithms for Dynamic DFS in Undirected Graphs
• Parallel Working-Set Search Structures

Cited by in corpus (13)

• Parallel Batch-Dynamic Graph Connectivity
• Parallel Batch-dynamic Trees via Change Propagation
• ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms
• CPMA: An Efficient Batch-Parallel Compressed Set Without Pointers
• Recent Advances in Fully Dynamic Graph Algorithms
• Input-Dynamic Distributed Algorithms for Communication Networks
• High-Performance and Flexible Parallel Algorithms for Semisort and Related Problems
• Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths
• How fast can you update your MST? (Dynamic algorithms for cluster computing)
• Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds
• Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees
• A Scalable Concurrent Algorithm for Dynamic Connectivity
• Parallel Batch-Dynamic Algorithms for Spanners, and Extensions