Document Open Access Logo

Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs

Author Aaron Bernstein



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.44.pdf
  • Filesize: 456 kB
  • 14 pages

Document Identifiers

Author Details

Aaron Bernstein

Cite AsGet BibTex

Aaron Bernstein. Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ICALP.2017.44

Abstract

In this paper we consider the decremental single-source shortest paths (SSSP) problem, where given a graph G and a source node s the goal is to maintain shortest distances between s and all other nodes in G under a sequence of online adversarial edge deletions. In their seminal work, Even and Shiloach [JACM 1981] presented an exact solution to the problem in unweighted graphs with only O(mn) total update time over all edge deletions. Their classic algorithm was the state of the art for the decremental SSSP problem for three decades, even when approximate shortest paths are allowed. The first improvement over the Even-Shiloach algorithm was given by Bernstein and Roditty [SODA 2011], who for the case of an unweighted and undirected graph presented a (1+epsilon)-approximate algorithm with constant query time and a total update time of O(n^{2+o(1)}). This work triggered a series of new results, culminating in a recent breakthrough of Henzinger, Krinninger and Nanongkai [FOCS 14], who presented a (1+epsilon)-approximate algorithm for undirected weighted graphs whose total update time is near linear: O(m^{1+o(1)} log(W)), where W is the ratio of the heaviest to the lightest edge weight in the graph. In this paper they posed as a major open problem the question of derandomizing their result. Until very recently, all known improvements over the Even-Shiloach algorithm were randomized and required the assumption of a non-adaptive adversary. In STOC 2016, Bernstein and Chechik showed the first deterministic algorithm to go beyond O(mn) total update time: the algorithm is also (1+\epsilon)-approximate, and has total update time \tilde{O}(n^2). In SODA 2017, the same authors presented an algorithm with total update time \tilde{O}(mn^{3/4}). However, both algorithms are restricted to undirected, unweighted graphs. We present the first deterministic algorithm for weighted undirected graphs to go beyond the O(mn) bound. The total update time is \tilde{O}(n^2 \log(W)).
Keywords
  • Shortest Paths
  • Dynamic Algorithms
  • Deterministic
  • Weighted Graph

Metrics

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

References

  1. Ittai Abraham, Shiri Chechik, and Kunal Talwar. Fully dynamic all-pairs shortest paths: Breaking the o(n) barrier. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain, pages 1-16, 2014. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.1.
  2. Surender Baswana, Ramesh Hariharan, and Sandeep Sen. Maintaining all-pairs approximate shortest paths under deletion of edges. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 394-403. Society for Industrial and Applied Mathematics, 2003. URL: http://dl.acm.org/citation.cfm?id=644108.644171.
  3. Aaron Bernstein. Fully dynamic (2 + epsilon) approximate all-pairs shortest paths with fast query and close to linear update time. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 693-702, 2009. URL: http://dx.doi.org/10.1109/FOCS.2009.16.
  4. Aaron Bernstein and Shiri Chechik. Deterministic decremental single source shortest paths: beyond the o(mn) bound. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), pages 389-397, 2016. URL: http://dx.doi.org/10.1145/2897518.2897521.
  5. 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, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 453-469, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.29.
  6. 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, SODA, pages 1355-1365, 2011. URL: http://dx.doi.org/10.1137/1.9781611973082.104.
  7. Yefim Dinitz. Dinitz' algorithm: The original version and even’s version. In Theoretical Computer Science, Essays in Memory of Shimon Even, pages 218-240, 2006. URL: http://dx.doi.org/10.1007/11685654_10.
  8. Shimon Even and Yossi Shiloach. An on-line edge-deletion problem. Journal of the ACM, 28(1):1-4, 1981. URL: http://dx.doi.org/10.1145/322234.322235.
  9. Monika Henzinger and Valerie King. Fully dynamic biconnectivity and transitive closure. In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, 23-25 October 1995, pages 664-672, 1995. URL: http://dx.doi.org/10.1109/SFCS.1995.492668.
  10. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Dynamic approximate all-pairs shortest paths: Breaking the o(mn) barrier and derandomization. In Proceedings of the 54th Annual Symposium on Foundations of Computer Science, FOCS, pages 538-547, 2013. URL: http://dx.doi.org/10.1109/FOCS.2013.64.
  11. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Decremental single-source shortest paths on undirected graphs in near-linear total update time. In Proceedings of the 55th Annual Symposium on Foundations of Computer Science, FOCS, pages 146-155, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.24.
  12. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), pages 674-683, 2014. URL: http://dx.doi.org/10.1145/2591796.2591869.
  13. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. A subquadratic-time algorithm for decremental single-source shortest paths. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1053-1072, 2014. URL: http://dl.acm.org/citation.cfm?id=2634074.2634153.
  14. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Improved algorithms for decremental single-source reachability on directed graphs. In Proceedings of the 42nd International Colloquium, ICALP, pages 725-736, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_59.
  15. 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), pages 21-30, 2015. URL: http://dx.doi.org/10.1145/2746539.2746609.
  16. Monika Rauch Henzinger and Valerie King. Maintaining minimum spanning forests in dynamic graphs. SIAM J. Comput., 31(2):364-374, 2001. URL: http://dx.doi.org/10.1137/S0097539797327209.
  17. Valerie King. Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, FOCS, pages 81-91, 1999. URL: http://dl.acm.org/citation.cfm?id=795665.796487.
  18. Aleksander Madry. Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 121-130, 2010. URL: http://dx.doi.org/10.1145/1806689.1806708.
  19. Liam Roditty and Uri Zwick. On dynamic shortest paths problems. Algorithmica, 61(2):389-401, 2011. URL: http://dx.doi.org/10.1007/s00453-010-9401-5.
  20. Liam Roditty and Uri Zwick. Dynamic approximate all-pairs shortest paths in undirected graphs. SIAM J. Comput., 41(3):670-683, 2012. URL: http://dx.doi.org/10.1137/090776573.
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