Document Open Access Logo

Simplifying and Unifying Replacement Paths Algorithms in Weighted Directed Graphs

Authors Shiri Chechik, Moran Nechushtan

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.29.pdf
  • Filesize: 0.86 MB
  • 12 pages

Document Identifiers

Author Details

Shiri Chechik
  • Blavatnik School of Computer Science, Tel Aviv University, Israel
Moran Nechushtan
  • 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).

Acknowledgements

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 As Get BibTex

Shiri Chechik and Moran Nechushtan. Simplifying and Unifying Replacement Paths Algorithms in Weighted Directed Graphs. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 29:1-29:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICALP.2020.29

Abstract

In the replacement paths (RP) problem we are given a graph G and a shortest path P between two nodes s and t . The goal is to find for every edge e ∈ P, a shortest path from s to t that avoids e. The first result of this paper is a simple reduction from the RP problem to the problem of computing shortest cycles for all nodes on a shortest path.
Using this simple reduction we unify and extremely simplify two state of the art solutions for two different well-studied variants of the RP problem.
In the first variant (algebraic) we show that by using at most n queries to the Yuster-Zwick distance oracle [FOCS 2005], one can solve the the RP problem for a given directed graph with integer edge weights in the range [-M,M] in Õ(M n^ω) time . This improves the running time of the state of the art algorithm of Vassilevska Williams [SODA 2011] by a factor of log⁶n.
In the second variant (planar) we show that by using the algorithm of Klein for the multiple-source shortest paths problem (MSSP) [SODA 2005] one can solve the RP problem for directed planar graph with non negative edge weights in O (n log n) time. This matches the state of the art algorithm of Wulff-Nilsen [SODA 2010], but with arguably much simpler algorithm and analysis.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Shortest paths
Keywords
  • Fault tolerance
  • Distance oracle
  • Planar graph

Metrics

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

References

  1. Udit Agarwal and Vijaya Ramachandran. Fine-grained complexity for sparse graphs. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 239-252, New York, NY, USA, 2018. ACM. URL: https://doi.org/10.1145/3188745.3188888.
  2. Noga Alon, Zvi Galil, and Oded Margalit. On the exponent of the all pairs shortest path problem. Journal of Computer and System Sciences, 54(2):255-262, 1997. Google Scholar
  3. Yuval Emek, David Peleg, and Liam Roditty. A near-linear-time algorithm for computing replacement paths in planar directed graphs. ACM Transactions on Algorithms (TALG), 6(4):64, 2010. Google Scholar
  4. David Eppstein. Finding the k shortest paths. SIAM Journal on computing, 28(2):652-673, 1998. Google Scholar
  5. Zvi Gotthilf and Moshe Lewenstein. Improved algorithms for the k simple shortest paths and the replacement paths problems. Information Processing Letters, 109(7):352-355, 2009. Google Scholar
  6. Monika R Henzinger, Philip Klein, Satish Rao, and Sairam Subramanian. Faster shortest-path algorithms for planar graphs. journal of computer and system sciences, 55(1):3-23, 1997. Google Scholar
  7. John Hershberger and Subhash Suri. Vickrey prices and shortest paths: What is an edge worth? In Proceedings 2001 IEEE International Conference on Cluster Computing, pages 252-259. IEEE, 2001. Google Scholar
  8. John Hershberger, Subhash Suri, and Amit Bhosle. On the difficulty of some shortest path problems. In Annual Symposium on Theoretical Aspects of Computer Science, pages 343-354. Springer, 2003. Google Scholar
  9. 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. Google Scholar
  10. Philip Klein, Shay Mozes, and Oren Weimann. Shortest paths in directed planar graphs with negative lengths: A linear-space o (n log2 n)-time algorithm. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 236-245. SIAM, 2009. Google Scholar
  11. Philip N Klein. Multiple-source shortest paths in planar graphs. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 146-155. Society for Industrial and Applied Mathematics, 2005. Google Scholar
  12. Kavindra Malik, Ashok K Mittal, and Santosh K Gupta. The k most vital arcs in the shortest path problem. Operations Research Letters, 8(4):223-227, 1989. Google Scholar
  13. Shay Mozes and Christian Wulff-Nilsen. Shortest paths in planar graphs with real lengths in o (nlog 2 n/loglogn) time. In European Symposium on Algorithms, pages 206-217. Springer, 2010. Google Scholar
  14. Enrico Nardelli, Guido Proietti, and Peter Widmayer. A faster computation of the most vital edge of a shortest path? Information Processing Letters, 79(2):81-85, 2001. Google Scholar
  15. Noam Nisan and Amir Ronen. Algorithmic mechanism design. Games and Economic behavior, 35(1-2):166-196, 2001. Google Scholar
  16. Liam Roditty and Uri Zwick. Replacement paths and k simple shortest paths in unweighted directed graphs. In International Colloquium on Automata, Languages, and Programming, pages 249-260. Springer, 2005. Google Scholar
  17. Oren Weimann and Raphael Yuster. Replacement paths via fast matrix multiplication. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 655-662. IEEE, 2010. Google Scholar
  18. Virginia Vassilevska Williams. Faster replacement paths. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 1337-1346. Society for Industrial and Applied Mathematics, 2011. Google Scholar
  19. Virginia Vassilevska Williams and R Ryan Williams. Subcubic equivalences between path, matrix, and triangle problems. Journal of the ACM (JACM), 65(5):27, 2018. Google Scholar
  20. Christian Wulff-Nilsen. Solving the replacement paths problem for planar directed graphs in o (n log n) time. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 756-765. Society for Industrial and Applied Mathematics, 2010. Google Scholar
  21. Raphael Yuster and Uri Zwick. Answering distance queries in directed graphs using fast matrix multiplication. In Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on, pages 389-396. IEEE, 2005. 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