Document Open Access Logo

Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem

Authors Shiri Chechik, Ofer Magen

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.81.pdf
  • Filesize: 0.54 MB
  • 17 pages

Document Identifiers

Author Details

Shiri Chechik
  • Blavatnik School of Computer Science, Tel Aviv University, Israel
Ofer Magen
  • Blavatnik School of Computer Science, Tel Aviv University, Israel

Funding

This publication is part of a project that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 803118 UncertainENV).

Cite AsGet BibTex

Shiri Chechik and Ofer Magen. Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 81:1-81:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.81

Abstract

In the Single Source Replacement Paths (SSRP) problem we are given a graph G = (V, E), and a shortest paths tree K̂ rooted at a node s, and the goal is to output for every node t ∈ V and for every edge e in K̂ the length of the shortest path from s to t avoiding e. We present an Õ(m√n + n²) time randomized combinatorial algorithm for unweighted directed graphs. Previously such a bound was known in the directed case only for the seemingly easier problem of replacement path where both the source and the target nodes are fixed. Our new upper bound for this problem matches the existing conditional combinatorial lower bounds. Hence, (assuming these conditional lower bounds) our result is essentially optimal and completes the picture of the SSRP problem in the combinatorial setting. Our algorithm naturally extends to the case of small, rational edge weights. In the full version of the paper, we strengthen the existing conditional lower bounds in this case by showing that any O(mn^(1/2-ε)) time (combinatorial or algebraic) algorithm for some fixed ε > 0 yields a truly sub-cubic algorithm for the weighted All Pairs Shortest Paths problem (previously such a bound was known only for the combinatorial setting).

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
Keywords
  • Fault tolerance
  • Replacement Paths
  • Combinatorial algorithms
  • Conditional lower bounds

Metrics

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

Related Versions

References

  1. Noga Alon, Zvi Galil, and Oded Margalit. On the exponent of the all pairs shortest path problem. J. Comput. Syst. Sci., 54(2):255-262, April 1997. URL: https://doi.org/10.1006/jcss.1997.1388.
  2. Shiri Chechik and Sarel Cohen. Near optimal algorithms for the single source replacement paths problem. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '19, pages 2090-2109, Philadelphia, PA, USA, 2019. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=3310435.3310561.
  3. Yuval Emek, David Peleg, and Liam Roditty. A near-linear time algorithm for computing replacement paths in planar directed graphs. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '08, pages 428-435, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347129.
  4. David Eppstein. Finding the k shortest paths. SIAM Journal on Computing, 28(2):652-673, 1998. URL: https://doi.org/10.1137/S0097539795290477.
  5. F. Grandoni and V. V. Williams. Improved distance sensitivity oracles via fast single-source replacement paths. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 748-757, October 2012. URL: https://doi.org/10.1109/FOCS.2012.17.
  6. J. Hershberger and S. Suri. Vickrey prices and shortest paths: what is an edge worth? In Proceedings 2001 IEEE International Conference on Cluster Computing, pages 252-259, October 2001. URL: https://doi.org/10.1109/SFCS.2001.959899.
  7. John Hershberger, Subhash Suri, and Amit Bhosle. On the difficulty of some shortest path problems. ACM Trans. Algorithms, 3(1):5:1-5:15, February 2007. URL: https://doi.org/10.1145/1186810.1186815.
  8. David R. Karger, Daphne Koller, and Steven J. Phillips. Finding the hidden path: Time bounds for all-pairs shortest paths. SIAM Journal on Computing, 22(6):1199-1217, 1993. URL: https://doi.org/10.1137/0222071.
  9. Philip N. Klein, Shay Mozes, and Oren Weimann. Shortest paths in directed planar graphs with negative lengths: A linear-space o(n log²n)-time algorithm. ACM Trans. Algorithms, 6(2):30:1-30:18, April 2010. URL: https://doi.org/10.1145/1721837.1721846.
  10. François Le Gall. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC '14, pages 296-303, New York, NY, USA, 2014. ACM. URL: https://doi.org/10.1145/2608628.2608664.
  11. K. Malik, A. K. Mittal, and S. K. Gupta. The k most vital arcs in the shortest path problem. Oper. Res. Lett., 8(4):223-227, August 1989. URL: https://doi.org/10.1016/0167-6377(89)90065-5.
  12. Enrico Nardelli, Guido Proietti, and Peter Widmayer. A faster computation of the most vital edge of a shortest path. Inf. Process. Lett., 79(2):81-85, June 2001. URL: https://doi.org/10.1016/S0020-0190(00)00175-7.
  13. Enrico Nardelli, Guido Proietti, and Peter Widmayer. Finding the most vital node of a shortest path. Theor. Comput. Sci., 296(1):167-177, March 2003. URL: https://doi.org/10.1016/S0304-3975(02)00438-3.
  14. Noam Nisan and Amir Ronen. Algorithmic mechanism design (extended abstract). In Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing, STOC '99, pages 129-140, New York, NY, USA, 1999. ACM. URL: https://doi.org/10.1145/301250.301287.
  15. Liam Roditty and Uri Zwick. Replacement paths and k simple shortest paths in unweighted directed graphs. ACM Trans. Algorithms, 8(4):33:1-33:11, October 2012. URL: https://doi.org/10.1145/2344422.2344423.
  16. Virginia Vassilevska Williams. Faster replacement paths. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’11, page 1337–1346, USA, 2011. Society for Industrial and Applied Mathematics. Google Scholar
  17. Virginia Vassilevska Williams. Multiplying matrices faster than coppersmith-winograd. In Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC '12, pages 887-898, New York, NY, USA, 2012. ACM. URL: https://doi.org/10.1145/2213977.2214056.
  18. Virginia Vassilevska Williams and R. Ryan Williams. Subcubic equivalences between path, matrix, and triangle problems. J. ACM, 65(5), August 2018. URL: https://doi.org/10.1145/3186893.
  19. Christian Wulff-Nilsen. Solving the replacement paths problem for planar directed graphs in o(n logn) time. In Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '10, pages 756-765, 2010. URL: http://dl.acm.org/citation.cfm?id=1873601.1873663.
  20. Gideon Yuval. An algorithm for finding all shortest paths using n^2.81 infinite-precision multiplications. Inf. Process. Lett., 4:155-156, 1976. Google Scholar
  21. Uri Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication. Journal of the ACM, 49(3):289–317, May 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 Imprint Privacy Contact