Document Open Access Logo

Near-Optimal Decremental Hopsets with Applications

Authors Jakub Łącki, Yasamin Nazari

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.86.pdf
  • Filesize: 0.78 MB
  • 20 pages

Document Identifiers

Author Details

Jakub Łącki
  • Google Research, New York, NY, USA
Yasamin Nazari
  • Universität Salzburg, Austria

Funding

  • Nazari, Yasamin: This work was conducted in part while the author was an intern at Google and a PhD student at Johns Hopkins University. Supported in part by NSF award CCF-1909111 and by Austrian Science Fund (FWF) grant P 32863-N.

Acknowledgements

The authors would like to thank Michael Dinitz and Sebastian Forster for the helpful discussions.

Cite As Get BibTex

Jakub Łącki and Yasamin Nazari. Near-Optimal Decremental Hopsets with Applications. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 86:1-86:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ICALP.2022.86

Abstract

Given a weighted undirected graph G = (V,E,w), a hopset H of hopbound β and stretch (1+ε) is a set of edges such that for any pair of nodes u, v ∈ V, there is a path in G ∪ H of at most β hops, whose length is within a (1+ε) factor from the distance between u and v in G. We show the first efficient decremental algorithm for maintaining hopsets with a polylogarithmic hopbound. The update time of our algorithm matches the best known static algorithm up to polylogarithmic factors. All the previous decremental hopset constructions had a superpolylogarithmic (but subpolynomial) hopbound of 2^{log^{Ω(1)} n} [Bernstein, FOCS'09; HKN, FOCS'14; Chechik, FOCS'18].
By applying our decremental hopset construction, we get improved or near optimal bounds for several distance problems. Most importantly, we show how to decrementally maintain (2k-1)(1+ε)-approximate all-pairs shortest paths (for any constant k ≥ 2), in Õ(n^{1/k}) amortized update time and O(k) query time. This improves (by a polynomial factor) over the update-time of the best previously known decremental algorithm in the constant query time regime. Moreover, it improves over the result of [Chechik, FOCS'18] that has a query time of O(log log(nW)), where W is the aspect ratio, and the amortized update time is n^{1/k}⋅(1/ε)^{Õ(√{log n})}). For sparse graphs our construction nearly matches the best known static running time / query time tradeoff. 
We also obtain near-optimal bounds for maintaining approximate multi-source shortest paths and distance sketches, and get improved bounds for approximate single-source shortest paths. Our algorithms are randomized and our bounds hold with high probability against an oblivious adversary.

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
Keywords
  • Dynamic Algorithms
  • Data Structures
  • Shortest Paths
  • Hopsets

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Amir Abboud, Greg Bodwin, and Seth Pettie. A hierarchy of lower bounds for sublinear additive spanners. SIAM Journal on Computing, 47(6):2203-2236, 2018. Google Scholar
  2. Alexandr Andoni, Clifford Stein, and Peilin Zhong. Parallel approximate undirected shortest paths via low hop emulators. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 322-335, 2020. Google Scholar
  3. Ruben Becker, Sebastian Forster, Andreas Karrenbauer, and Christoph Lenzen. Near-optimal approximate shortest paths and transshipment in distributed and streaming models. SIAM Journal on Computing, 50(3):815-856, 2021. Google Scholar
  4. Uri Ben-Levy and Merav Parter. New (α, β) spanners and hopsets. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1695-1714. SIAM, 2020. Google Scholar
  5. Aaron Bernstein. Fully dynamic (2+ ε) approximate all-pairs shortest paths with fast query and close to linear update time. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 693-702. IEEE, 2009. Google Scholar
  6. Aaron Bernstein. Deterministic partially dynamic single source shortest paths in weighted graphs. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, page 44. Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017. Google Scholar
  7. Aaron Bernstein and Shiri Chechik. Deterministic partially dynamic single source shortest paths for sparse graphs. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 453-469. SIAM, 2017. Google Scholar
  8. Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak. Deterministic decremental sssp and approximate min-cost flow in almost-linear time. In 62 Annual IEEE Symposium on Foundatios of Computer Science (FOCS 2022), 2021. Google Scholar
  9. Aaron Bernstein and Liam Roditty. Improved dynamic algorithms for maintaining approximate shortest paths under deletions. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 1355-1365. SIAM, 2011. Google Scholar
  10. Keren Censor-Hillel, Michal Dory, Janne H Korhonen, and Dean Leitersdorf. Fast approximate shortest paths in the congested clique. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 74-83, 2019. Google Scholar
  11. Shiri Chechik. Approximate distance oracles with constant query time. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 654-663, 2014. Google Scholar
  12. Shiri Chechik. Near-optimal approximate decremental all pairs shortest paths. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 170-181. IEEE, 2018. Google Scholar
  13. Edith Cohen. Polylog-time and near-linear work approximation scheme for undirected shortest paths. Journal of the ACM (JACM), 2000. Google Scholar
  14. Michael Dinitz and Yasamin Nazari. Massively parallel approximate distance sketches. OPODIS, 2019. Google Scholar
  15. Michael Elkin, Yuval Gitlitz, and Ofer Neiman. Almost shortest paths and pram distance oracles in weighted graphs. arXiv preprint, 2019. URL: http://arxiv.org/abs/1907.11422.
  16. Michael Elkin and Ofer Neiman. Near-optimal distributed routing with low memory. In Proceedings of the ACM Symposium on Principles of Distributed Computing. ACM, 2018. Google Scholar
  17. Michael Elkin and Ofer Neiman. Hopsets with constant hopbound, and applications to approximate shortest paths. SIAM Journal on Computing, 2019. Google Scholar
  18. Michael Elkin and Ofer Neiman. Linear-size hopsets with small hopbound, and constant-hopbound hopsets in rnc. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures, pages 333-341, 2019. Google Scholar
  19. Michael Elkin and Ofer Neiman. Near-additive spanners and near-exact hopsets, a unified view. arXiv preprint, 2020. URL: http://arxiv.org/abs/2001.07477.
  20. Maximilian Probst Gutenberg and Christian Wulff-Nilsen. Deterministic algorithms for decremental approximate shortest paths: Faster and simpler. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2522-2541. SIAM, 2020. Google Scholar
  21. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Decremental single-source shortest paths on undirected graphs in near-linear total update time. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 146-155. IEEE, 2014. Google Scholar
  22. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Dynamic approximate all-pairs shortest paths: Breaking the o(mn) barrier and derandomization. SIAM Journal on Computing, 45(3):947-1006, 2016. Google Scholar
  23. Shang-En Huang and Seth Pettie. Thorup-zwick emulators are universally optimal hopsets. Information Processing Letters, 142:9-13, 2019. Google Scholar
  24. Philip N Klein and Sairam Subramanian. A randomized parallel algorithm for single-source shortest paths. Journal of Algorithms, 1997. Google Scholar
  25. Jason Li. Faster parallel algorithm for approximate shortest path. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 308-321, 2020. Google Scholar
  26. Aleksander Madry. Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 121-130, 2010. Google Scholar
  27. Manor Mendel and Assaf Naor. Ramsey partitions and proximity data structures. Journal of the European Mathematical Society, 9(2):253-275, 2007. Google Scholar
  28. Gary L Miller, Richard Peng, Adrian Vladu, and Shen Chen Xu. Improved parallel algorithms for spanners and hopsets. In Proceedings of the Symposium on Parallelism in Algorithms and Architectures. ACM, 2015. Google Scholar
  29. Danupon Nanongkai. Distributed approximation algorithms for weighted shortest paths. In Proceedings of the ACM Symposium on Theory of computing. ACM, 2014. Google Scholar
  30. Liam Roditty, Mikkel Thorup, and Uri Zwick. Deterministic constructions of approximate distance oracles and spanners. In International Colloquium on Automata, Languages, and Programming, pages 261-272. Springer, 2005. Google Scholar
  31. Liam Roditty and Uri Zwick. Dynamic approximate all-pairs shortest paths in undirected graphs. In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 499-508. IEEE, 2004. Google Scholar
  32. Atish Das Sarma, Michael Dinitz, and Gopal Pandurangan. Efficient distributed computation of distance sketches in networks. Distributed Computing, 28(5):309-320, 2015. Google Scholar
  33. Yossi Shiloach and Shimon Even. An on-line edge-deletion problem. Journal of the ACM (JACM), 28(1):1-4, 1981. Google Scholar
  34. Mikkel Thorup and Uri Zwick. Approximate distance oracles. Journal of the ACM (JACM), 52(1):1-24, 2005. Google Scholar
  35. Mikkel Thorup and Uri Zwick. Spanners and emulators with sublinear distance errors. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 802-809, 2006. Google Scholar
  36. Christian Wulff-Nilsen. Approximate distance oracles with improved preprocessing time. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 202-208. SIAM, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact