Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
Preprint
Abstract
Whether a graph $G=(V,E)$ is connected is arguably its most fundamental property. Naturally, connectivity was the first characteristic studied for dynamic graphs, i.e. graphs that undergo edge insertions and deletions. While connectivity algorithms with polylogarithmic amortized update time have been known since the 90s, achieving worst-case guarantees has proven more elusive. Two recent breakthroughs have made important progress on this question: (1) Kapron, King and Mountjoy [SODA'13; Best Paper] gave a Monte-Carlo algorithm with polylogarithmic worst-case update time, and (2) Nanongkai, Saranurak and Wulff-Nilsen [STOC'17, FOCS'17] obtained a Las-Vegas data structure, however, with subpolynomial worst-case update time. Their algorithm was subsequently de-randomized [FOCS'20]. In this article, we present a new dynamic connectivity algorithm based on the popular core graph framework that maintains a hierarchy interleaving vertex and edge sparsification. Previous dynamic implementations of the core graph framework required subpolynomial update time. In contrast, we show how to implement it for dynamic connectivity with polylogarithmic expected worst-case update time. We further show that the algorithm can be de-randomized efficiently: a deterministic static algorithm for computing a connectivity edge-sparsifier of low congestion in time $T(m) \cdot m$ on an $m$-edge graph yields a deterministic dynamic connectivity algorithm with $\tilde{O}(T(m))$ worst-case update time. Via current state-of-the-art algorithms [STOC'24], we obtain $T(m) = m^{o(1)}$ and recover deterministic subpolynomial worst-case update time.
Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Expander Decomposition and Pruning: Faster, Stronger, and Simpler2019
- Maintaining information in fully dynamic trees with top treesACM Transactions on Algorithms, 2005
- Sparsification—a technique for speeding up dynamic graph algorithmsJournal of the ACM, 1997
- Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning TreesSIAM Journal on Computing, 1997
- Algorithms for updating minimal spanning treesJournal of Computer and System Sciences, 1978
- On Finding and Updating Spanning Trees and Shortest PathsSIAM Journal on Computing, 1975