New techniques and fine-grained hardness for dynamic near-additive spanners
Bergamaschi T, Henzinger MH, Gutenberg MP, Williams VV, Wein N. 2021. New techniques and fine-grained hardness for dynamic near-additive spanners. 32nd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1836–1855.
Download (ext.)
https://arxiv.org/abs/2010.10134
[Preprint]
Conference Paper
| Published
| English
Scopus indexed
Author
Bergamaschi, Thiago;
Henzinger, MonikaISTA ;
Gutenberg, Maximilian Probst;
Williams, Virginia Vassilevska;
Wein, Nicole
Abstract
Maintaining and updating shortest paths information in a graph is a fundamental problem with many applications. As computations on dense graphs can be prohibitively expensive, and it is preferable to perform the computations on a sparse skeleton of the given graph that roughly preserves the shortest paths information. Spanners and emulators serve this purpose. Unfortunately, very little is known about dynamically maintaining sparse spanners and emulators as the graph is modified by a sequence of edge insertions and deletions. This paper develops fast dynamic algorithms for spanner and emulator maintenance and provides evidence from fine-grained complexity that these algorithms are tight. For unweighted undirected m-edge n-node graphs we obtain the following results.
Under the popular OMv conjecture, there can be no decremental or incremental algorithm that maintains an n1+o(1) edge (purely additive) +nδ-emulator for any δ < 1/2 with arbitrary polynomial preprocessing time and total update time m1+o(1). Also, under the Combinatorial k-Clique hypothesis, any fully dynamic combinatorial algorithm that maintains an n1+o(1) edge (1 + ∊, no(1))-spanner or emulator for small ∊ must either have preprocessing time mn1–o(1) or amortized update time m1–o(1). Both of our conditional lower bounds are tight.
As the above fully dynamic lower bound only applies to combinatorial algorithms, we also develop an algebraic spanner algorithm that improves over the m1–o(1) update time for dense graphs. For any constant ∊ ∊ (0, 1], there is a fully dynamic algorithm with worst-case update time O(n1.529) that whp maintains an n1+o(1) edge (1 + ∊, no(1))-spanner.
Our new algebraic techniques allow us to also obtain a new fully dynamic algorithm for All-Pairs Shortest Paths (APSP) that can perform both edge updates and can report shortest paths in worst-case time O(n1.9), which are correct whp. This is the first path-reporting fully dynamic APSP algorithm with a truly subquadratic query time that beats O(n2.5) update time. It works against an oblivious adversary.
Finally, we give two applications of our new dynamic spanner algorithms: (1) a fully dynamic (1 + ∊)-approximate APSP algorithm with update time O(n1.529) that can report approximate shortest paths in n1+o(1) time per query; previous subquadratic update/query algorithms could only report the distance, but not obtain the paths; (2) a fully dynamic algorithm for near-2-approximate Steiner tree maintenance with both terminal and edge updates.
Publishing Year
Date Published
2021-01-01
Proceedings Title
32nd Annual ACM-SIAM Symposium on Discrete Algorithms
Publisher
Society for Industrial and Applied Mathematics
Page
1836-1855
Conference
SODA: Symposium on Discrete Algorithms
Conference Location
Alexandria, VA, United States
Conference Date
2021-01-10 – 2021-01-13
IST-REx-ID
Cite this
Bergamaschi T, Henzinger MH, Gutenberg MP, Williams VV, Wein N. New techniques and fine-grained hardness for dynamic near-additive spanners. In: 32nd Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2021:1836-1855. doi:10.1137/1.9781611976465.110
Bergamaschi, T., Henzinger, M. H., Gutenberg, M. P., Williams, V. V., & Wein, N. (2021). New techniques and fine-grained hardness for dynamic near-additive spanners. In 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1836–1855). Alexandria, VA, United States: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611976465.110
Bergamaschi, Thiago, Monika H Henzinger, Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein. “New Techniques and Fine-Grained Hardness for Dynamic near-Additive Spanners.” In 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, 1836–55. Society for Industrial and Applied Mathematics, 2021. https://doi.org/10.1137/1.9781611976465.110.
T. Bergamaschi, M. H. Henzinger, M. P. Gutenberg, V. V. Williams, and N. Wein, “New techniques and fine-grained hardness for dynamic near-additive spanners,” in 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, Alexandria, VA, United States, 2021, pp. 1836–1855.
Bergamaschi T, Henzinger MH, Gutenberg MP, Williams VV, Wein N. 2021. New techniques and fine-grained hardness for dynamic near-additive spanners. 32nd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1836–1855.
Bergamaschi, Thiago, et al. “New Techniques and Fine-Grained Hardness for Dynamic near-Additive Spanners.” 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2021, pp. 1836–55, doi:10.1137/1.9781611976465.110.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2010.10134