Document Open Access Logo

Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs

Authors Adam Karczmarz , Jakub Łącki

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.65.pdf
  • Filesize: 0.51 MB
  • 15 pages

Document Identifiers

Author Details

Adam Karczmarz
  • Institute of Informatics, University of Warsaw, Poland
Jakub Łącki
  • Google Research, New York, USA

Funding

  • Karczmarz, Adam: Supported by ERC Consolidator Grant 772346 TUgbOAT and the Polish National Science Centre 2018/29/N/ST6/00757 grant.

Cite As Get BibTex

Adam Karczmarz and Jakub Łącki. Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 65:1-65:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ESA.2019.65

Abstract

We give new partially-dynamic algorithms for the all-pairs shortest paths problem in weighted directed graphs. Most importantly, we give a new deterministic incremental algorithm for the problem that handles updates in O~(mn^(4/3) log{W}/epsilon) total time (where the edge weights are from [1,W]) and explicitly maintains a (1+epsilon)-approximate distance matrix. For a fixed epsilon>0, this is the first deterministic partially dynamic algorithm for all-pairs shortest paths in directed graphs, whose update time is o(n^2) regardless of the number of edges. Furthermore, we also show how to improve the state-of-the-art partially dynamic randomized algorithms for all-pairs shortest paths [Baswana et al. STOC’02, Bernstein STOC’13] from Monte Carlo randomized to Las Vegas randomized without increasing the running time bounds (with respect to the O~(*) notation).
Our results are obtained by giving new algorithms for the problem of dynamically maintaining hubs, that is a set of O~(n/d) vertices which hit a shortest path between each pair of vertices, provided it has hop-length Omega(d). We give new subquadratic deterministic and Las Vegas algorithms for maintenance of hubs under either edge insertions or deletions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
Keywords
  • shortest paths
  • dynamic
  • incremental
  • decremental
  • directed graphs
  • hubs

Metrics

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

Related Versions

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, Philadelphia, PA, USA, October 18-21, 2014, pages 434-443, 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 Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 440-452. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974782.28.
  3. Giorgio Ausiello, Giuseppe F. Italiano, Alberto Marchetti-Spaccamela, and Umberto Nanni. Incremental Algorithms for Minimal Length Paths. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 22-24 January 1990, San Francisco, California, USA., pages 12-21, 1990. URL: http://dl.acm.org/citation.cfm?id=320176.320178.
  4. 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.
  5. 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.
  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 2011, San Francisco, California, USA, January 23-25, 2011, pages 1355-1365, 2011. URL: https://doi.org/10.1137/1.9781611973082.104.
  7. Camil Demetrescu and Giuseppe F. Italiano. Fully Dynamic Transitive Closure: Breaking Through the O(n²) Barrier. In 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA, pages 381-389, 2000. URL: https://doi.org/10.1109/SFCS.2000.892126.
  8. 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.
  9. Camil Demetrescu and Giuseppe F. Italiano. Fully dynamic all pairs shortest paths with real edge weights. J. Comput. Syst. Sci., 72(5):813-837, 2006. URL: https://doi.org/10.1016/j.jcss.2005.05.005.
  10. Shimon Even and Yossi Shiloach. An On-Line Edge-Deletion Problem. J. ACM, 28(1):1-4, 1981. URL: https://doi.org/10.1145/322234.322235.
  11. 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 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1053-1072, 2014. URL: https://doi.org/10.1137/1.9781611973402.79.
  12. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 674-683, 2014. URL: https://doi.org/10.1145/2591796.2591869.
  13. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 725-736, 2015. URL: https://doi.org/10.1007/978-3-662-47672-7_59.
  14. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization. SIAM J. Comput., 45(3):947-1006, 2016. URL: https://doi.org/10.1137/140957299.
  15. Monika Rauch Henzinger and Valerie King. Fully Dynamic Biconnectivity and Transitive Closure. In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, pages 664-672, 1995. URL: https://doi.org/10.1109/SFCS.1995.492668.
  16. Monika Rauch Henzinger and Valerie King. Randomized dynamic graph algorithms with polylogarithmic time per operation. In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 29 May-1 June 1995, Las Vegas, Nevada, USA, pages 519-527, 1995. URL: https://doi.org/10.1145/225058.225269.
  17. Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM, 48(4):723-760, 2001. URL: https://doi.org/10.1145/502090.502095.
  18. Bruce M. Kapron, Valerie King, and Ben Mountjoy. Dynamic graph connectivity in polylogarithmic worst case time. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1131-1142, 2013. URL: https://doi.org/10.1137/1.9781611973105.81.
  19. 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 '99, 17-18 October, 1999, New York, NY, USA, pages 81-91, 1999. URL: https://doi.org/10.1109/SFFCS.1999.814580.
  20. 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.
  21. 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.
  22. Liam Roditty and Uri Zwick. Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs. SIAM J. Comput., 41(3):670-683, 2012. URL: https://doi.org/10.1137/090776573.
  23. Piotr Sankowski. Dynamic Transitive Closure via Dynamic Matrix Inverse (Extended Abstract). In 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings, pages 509-517, 2004. URL: https://doi.org/10.1109/FOCS.2004.25.
  24. Daniel Dominic Sleator and Robert Endre Tarjan. A Data Structure for Dynamic Trees. J. Comput. Syst. Sci., 26(3):362-391, 1983. URL: https://doi.org/10.1016/0022-0000(83)90006-5.
  25. Robert Endre Tarjan. Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm. Math. Program., 77:169-177, 1997. URL: https://doi.org/10.1007/BF02614369.
  26. Mikkel Thorup. Near-optimal fully-dynamic graph connectivity. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 343-350, 2000. URL: https://doi.org/10.1145/335305.335345.
  27. 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.
  28. Christian Wulff-Nilsen. Faster Deterministic Fully-Dynamic Graph Connectivity. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1757-1769, 2013. URL: https://doi.org/10.1137/1.9781611973105.126.
  29. 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