New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners
New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners
复制标题
动态近增材扳手的新技术和细粒度硬度
DOI：
10.1137/1.9781611976465.110
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Wein, Nicole
中科院分区：
文献类型：
--
作者：
Bergamaschi, Thiago;Henzinger, Monika;Probst Gutenberg, Maximilian;Williams, Virginia Vassilevska;Wein, Nicole
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 undirectedm-edgen-node graphs we obtain the following results.Under the popular OMv conjecture, there can be no decremental or incremental algorithm that maintains ann1+o(1)edge (purely additive) +nδ-emulator for anyδ< 1/2 with arbitrary polynomial preprocessing time and total update timem1+o(1). Also, under the Combinatorialk-Clique hypothesis, any fully dynamic combinatorial algorithm that maintains ann1+o(1)edge (1 + ∊,no(1))-spanner or emulator for small ∊ must either have preprocessing timemn1–o(1)or amortized update timem1–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 them1–o(1)update time for dense graphs. For any constant ∊ ∊ (0, 1], there is a fully dynamic algorithm with worst-case update timeO(n1.529) that whp maintains ann1+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 timeO(n1.9), which are correct whp. This is the firstpath-reportingfully dynamic APSP algorithm with a truly subquadratic query time that beatsO(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 timeO(n1.529) that can report approximate shortest paths inn1+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.
登录
查看更多内容
近乎最优的近似递减所有对最短路径
DOI：
10.1109/focs.2018.00025
发表时间：
2018
期刊：
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
S. Chechik
通讯作者：
S. Chechik
新型增材扳手
DOI：
--
发表时间：
2013
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
S. Chechik
通讯作者：
S. Chechik
近加法扳手和近精确 Hopsets，统一视图
DOI：
--
发表时间：
2020
期刊：
Bull. EATCS
影响因子：
--
作者：
Michael Elkin;Ofer Neiman
通讯作者：
Ofer Neiman
用于构造 T 形扳手和具有拉伸 t 的路径的快速算法
DOI：
--
发表时间：
1993
期刊：
Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science
影响因子：
--
作者：
E. Cohen
通讯作者：
E. Cohen
DOI：
10.1137/090776573
发表时间：
2004
期刊：
45th Annual IEEE Symposium on Foundations of Computer Science
影响因子：
--
作者：
L. Roditty;Uri Zwick
通讯作者：
Uri Zwick