Document Open Access Logo

Fully Dynamic Shortest Paths and Reachability in Sparse Digraphs

Authors Adam Karczmarz , Piotr Sankowski

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2023.84.pdf
  • Filesize: 0.76 MB
  • 20 pages

Document Identifiers

Author Details

Adam Karczmarz
  • University of Warsaw, Poland
  • IDEAS NCBR, Warsaw, Poland
Piotr Sankowski
  • University of Warsaw, Poland
  • IDEAS NCBR, Warsaw, Poland

Funding

  • Karczmarz, Adam: Partially supported by the ERC CoG grant TUgbOAT no 772346.
  • Sankowski, Piotr: Partially supported by the ERC CoG grant TUgbOAT no 772346 and National Science Center (NCN) grant no. 2020/37/B/ST6/04179.

Cite As Get BibTex

Adam Karczmarz and Piotr Sankowski. Fully Dynamic Shortest Paths and Reachability in Sparse Digraphs. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 84:1-84:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ICALP.2023.84

Abstract

We study the exact fully dynamic shortest paths problem. For real-weighted directed graphs, we show a deterministic fully dynamic data structure with Õ(mn^{4/5}) worst-case update time processing arbitrary s,t-distance queries in Õ(n^{4/5}) time. This constitutes the first non-trivial update/query tradeoff for this problem in the regime of sparse weighted directed graphs.
Moreover, we give a Monte Carlo randomized fully dynamic reachability data structure processing single-edge updates in Õ(n√m) worst-case time and queries in O(√m) time. For sparse digraphs, such a tradeoff has only been previously described with amortized update time [Roditty and Zwick, SIAM J. Comp. 2008].

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
  • Theory of computation → Shortest paths
Keywords
  • dynamic shortest paths
  • dynamic reachability
  • dynamic transitive closure

Metrics

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

References

  1. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, pages 434-443. IEEE Computer Society, 2014. URL: https://doi.org/10.1109/FOCS.2014.53.
  2. Ittai Abraham, Shiri Chechik, and Sebastian Krinninger. Fully dynamic all-pairs shortest paths with worst-case update-time revisited. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 440-452. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974782.28.
  3. Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, pages 522-539. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.32.
  4. Stephen Alstrup, Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Maintaining information in fully dynamic trees with top trees. ACM Trans. Algorithms, 1(2):243-264, 2005. URL: https://doi.org/10.1145/1103963.1103966.
  5. Giorgio Ausiello, Giuseppe F. Italiano, Alberto Marchetti-Spaccamela, and Umberto Nanni. Incremental algorithms for minimal length paths. J. Algorithms, 12(4):615-638, 1991. URL: https://doi.org/10.1016/0196-6774(91)90036-X.
  6. Surender Baswana, Ramesh Hariharan, and Sandeep Sen. Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths. J. Algorithms, 62(2):74-92, 2007. URL: https://doi.org/10.1016/j.jalgor.2004.08.004.
  7. Walter Baur and Volker Strassen. The complexity of partial derivatives. Theor. Comput. Sci., 22:317-330, 1983. URL: https://doi.org/10.1016/0304-3975(83)90110-X.
  8. Thiago Bergamaschi, Monika Henzinger, Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein. New techniques and fine-grained hardness for dynamic near-additive spanners. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, pages 1836-1855. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.110.
  9. Aaron Bernstein. Maintaining shortest paths under deletions in weighted directed graphs. SIAM J. Comput., 45(2):548-574, 2016. URL: https://doi.org/10.1137/130938670.
  10. Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak. Deterministic decremental SSSP and approximate min-cost flow in almost-linear time. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, pages 1000-1008. IEEE, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00100.
  11. David G. Cantor and Erich Kaltofen. On fast multiplication of polynomials over arbitrary algebras. Acta Informatica, 28(7):693-701, 1991. URL: https://doi.org/10.1007/BF01178683.
  12. Sílvia Casacuberta and Rasmus Kyng. Faster sparse matrix inversion and rank computation in finite fields. In 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, volume 215 of LIPIcs, pages 33:1-33:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.ITCS.2022.33.
  13. Shiri Chechik and Tianyi Zhang. Faster deterministic worst-case fully dynamic all-pairs shortest paths via decremental hop-restricted shortest paths. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, pages 87-99. SIAM, 2023. URL: https://doi.org/10.1137/1.9781611977554.ch4.
  14. Li Chen, Gramoz Goranci, Monika Henzinger, Richard Peng, and Thatchaphol Saranurak. Fast dynamic cuts, distances and effective resistances via vertex sparsifiers. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, pages 1135-1146. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00109.
  15. Julia Chuzhoy. Decremental all-pairs shortest paths in deterministic near-linear time. In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 626-639. ACM, 2021. URL: https://doi.org/10.1145/3406325.3451025.
  16. Camil Demetrescu and Giuseppe F. Italiano. A new approach to dynamic all pairs shortest paths. J. ACM, 51(6):968-992, 2004. URL: https://doi.org/10.1145/1039488.1039492.
  17. Camil Demetrescu and Giuseppe F. Italiano. Trade-offs for fully dynamic transitive closure on dags: breaking through the O(n²) barrier. J. ACM, 52(2):147-156, 2005. URL: https://doi.org/10.1145/1059513.1059514.
  18. Wayne Eberly, Mark Giesbrecht, Pascal Giorgi, Arne Storjohann, and Gilles Villard. Faster inversion and other black box matrix computations using efficient block projections. In Symbolic and Algebraic Computation, International Symposium, ISSAC 2007, Proceedings, pages 143-150. ACM, 2007. URL: https://doi.org/10.1145/1277548.1277569.
  19. Jacob Evald, Viktor Fredslund-Hansen, Maximilian Probst Gutenberg, and Christian Wulff-Nilsen. Decremental APSP in unweighted digraphs versus an adaptive adversary. In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, volume 198 of LIPIcs, pages 64:1-64:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.64.
  20. Sebastian Forster, Yasamin Nazari, and Maximilian Probst Gutenberg. Deterministic incremental APSP with polylogarithmic update time and stretch. CoRR, abs/2211.04217, 2022. URL: https://doi.org/10.48550/arXiv.2211.04217.
  21. Francois Le Gall and Florent Urrutia. Improved rectangular matrix multiplication using powers of the coppersmith-winograd tensor. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pages 1029-1046. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.67.
  22. Gene H Golub and Charles F Van Loan. Matrix computations. JHU press, 2013. Google Scholar
  23. Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein. New algorithms and hardness for incremental single-source shortest paths in directed graphs. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 153-166. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384236.
  24. Maximilian Probst Gutenberg and Christian Wulff-Nilsen. Fully-dynamic all-pairs shortest paths: Improved worst-case time and space bounds. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pages 2562-2574. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.156.
  25. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, pages 21-30. ACM, 2015. URL: https://doi.org/10.1145/2746539.2746609.
  26. Erich Kaltofen and Victor Y. Pan. Processor efficient parallel solution of linear systems over an abstract field. In Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA '91, pages 180-191. ACM, 1991. URL: https://doi.org/10.1145/113379.113396.
  27. Adam Karczmarz. Fully dynamic algorithms for minimum weight cycle and related problems. In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, volume 198 of LIPIcs, pages 83:1-83:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.83.
  28. Adam Karczmarz, Anish Mukherjee, and Piotr Sankowski. Subquadratic dynamic path reporting in directed graphs against an adaptive adversary. In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1643-1656. ACM, 2022. URL: https://doi.org/10.1145/3519935.3520058.
  29. Walter Keller-Gehrig. Fast algorithms for the characteristic polynomial. Theor. Comput. Sci., 36:309-317, 1985. URL: https://doi.org/10.1016/0304-3975(85)90049-0.
  30. Valerie King. Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In 40th Annual Symposium on Foundations of Computer Science, FOCS 1999, pages 81-91. IEEE Computer Society, 1999. URL: https://doi.org/10.1109/SFFCS.1999.814580.
  31. Veli Mäkinen, Alexandru I. Tomescu, Anna Kuosmanen, Topi Paavilainen, Travis Gagie, and Rayan Chikhi. Sparse dynamic programming on dags with small width. ACM Trans. Algorithms, 15(2):29:1-29:21, 2019. URL: https://doi.org/10.1145/3301312.
  32. Liam Roditty. A faster and simpler fully dynamic transitive closure. ACM Trans. Algorithms, 4(1):6:1-6:16, 2008. URL: https://doi.org/10.1145/1328911.1328917.
  33. Liam Roditty and Uri Zwick. Improved dynamic reachability algorithms for directed graphs. SIAM J. Comput., 37(5):1455-1471, 2008. URL: https://doi.org/10.1137/060650271.
  34. Liam Roditty and Uri Zwick. On dynamic shortest paths problems. Algorithmica, 61(2):389-401, 2011. URL: https://doi.org/10.1007/s00453-010-9401-5.
  35. Piotr Sankowski. Dynamic transitive closure via dynamic matrix inverse (extended abstract). In 45th Symposium on Foundations of Computer Science FOCS 2004, pages 509-517. IEEE Computer Society, 2004. URL: https://doi.org/10.1109/FOCS.2004.25.
  36. Mikkel Thorup. Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles. In Algorithm Theory - SWAT 2004, 9th Scandinavian Workshop on Algorithm Theory, Proceedings, volume 3111 of Lecture Notes in Computer Science, pages 384-396. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-27810-8_33.
  37. Jeffrey D. Ullman and Mihalis Yannakakis. High-probability parallel transitive-closure algorithms. SIAM J. Comput., 20(1):100-125, 1991. URL: https://doi.org/10.1137/0220006.
  38. Jan van den Brand, Sebastian Forster, and Yasamin Nazari. Fast deterministic fully dynamic distance approximation. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, pages 1011-1022. IEEE, 2022. URL: https://doi.org/10.1109/FOCS54457.2022.00099.
  39. Jan van den Brand and Danupon Nanongkai. Dynamic approximate shortest paths and beyond: Subquadratic and worst-case update time. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, pages 436-455. IEEE Computer Society, 2019. URL: https://doi.org/10.1109/FOCS.2019.00035.
  40. Jan van den Brand, Danupon Nanongkai, and Thatchaphol Saranurak. Dynamic matrix inverse: Improved algorithms and matching conditional lower bounds. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, pages 456-480. IEEE Computer Society, 2019. URL: https://doi.org/10.1109/FOCS.2019.00036.
  41. Douglas H. Wiedemann. Solving sparse linear equations over finite fields. IEEE Trans. Inf. Theory, 32(1):54-62, 1986. URL: https://doi.org/10.1109/TIT.1986.1057137.
  42. Uri Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM, 49(3):289-317, 2002. URL: https://doi.org/10.1145/567112.567114.
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