Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n1/2 - ε)-time

DOI10.1145/3055399.3055447zbMATH Open1370.68234arXiv1611.03745OpenAlexW2571471359MaRDI QIDQ4978052FDOQ4978052

Danupon Nanongkai, Thatchaphol Saranurak

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Abstract: We present two algorithms for dynamically maintaining a spanning forest of a graph undergoing edge insertions and deletions. Our algorithms guarantee {em worst-case update time} and work against an adaptive adversary, meaning that an edge update can depend on previous outputs of the algorithms. We provide the first polynomial improvement over the long-standing $O(sqrtn)$ bound of [Frederickson STOC'83, Eppstein, Galil, Italiano and Nissenzweig FOCS'92] for such type of algorithms. The previously best improvement was $O(sqrtn(loglogn{)}^2/logn)$ [Kejlberg-Rasmussen, Kopelowitz, Pettie and Thorup ESA'16]. We note however that these bounds were obtained by deterministic algorithms while our algorithms are randomized. Our first algorithm is Monte Carlo and guarantees an $O(n^{0.4+o(1)})$ worst-case update time, where the $o(1)$ term hides the $O(sqrtloglogn/logn)$ factor. Our second algorithm is Las Vegas and guarantees an $O(n^{0.49306})$ worst-case update time with high probability. Algorithms with better update time either needed to assume that the adversary is oblivious (e.g. [Kapron, King and Mountjoy SODA'13]) or can only guarantee an amortized update time. Our second result answers an open problem by Kapron et al. To the best of our knowledge, our algorithms are among a few non-trivial randomized dynamic algorithms that work against adaptive adversaries.

Full work available at URL: https://arxiv.org/abs/1611.03745

zbMATH Keywords

sparse recoverygraph decompositiondynamic spanning forestlocal graph partitioning

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (12)

• Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions
• Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
• Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
• Decremental SPQR-trees for Planar Graphs
• Good \(r\)-divisions imply optimal amortized decremental biconnectivity
• Faster connectivity in low-rank hypergraphs via expander decomposition
• Constant-time dynamic weight approximation for minimum spanning forest
• Deterministic dynamic matching in worst-case update time
• Fast algorithms via dynamic-oracle matroids
• Finding a small vertex cut on distributed networks
• Maximum length-constrained flows and disjoint paths: distributed, deterministic, and fast
• Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier

This page was built for publication: Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n^{1/2 - ε})-time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4978052)