Document Open Access Logo

Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles

Authors Noga Alon, Shiri Chechik, Sarel Cohen

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.12.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Author Details

Noga Alon
  • Department of Mathematics, Princeton University, Princeton, NJ 08544, USA
  • Schools of Mathematics and Computer Science, Tel Aviv University, Tel Aviv 69978, Israel
Shiri Chechik
  • Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel
Sarel Cohen
  • Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel

Funding

  • Alon, Noga: Research supported in part by NSF grant DMS-1855464, ISF grant 281/17 and GIF grant G-1347-304.6/2016.
  • Chechik, Shiri: Research supported in part by the Israel Science Foundation grant No. 1528/15 and the Blavatnik Fund.
  • Cohen, Sarel: Research supported in part by the Israel Science Foundation grant No. 1528/15 and the Blavatnik Fund.

Cite AsGet BibTex

Noga Alon, Shiri Chechik, and Sarel Cohen. Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.12

Abstract

In this work we derandomize two central results in graph algorithms, replacement paths and distance sensitivity oracles (DSOs) matching in both cases the running time of the randomized algorithms. For the replacement paths problem, let G = (V,E) be a directed unweighted graph with n vertices and m edges and let P be a shortest path from s to t in G. The replacement paths problem is to find for every edge e in P the shortest path from s to t avoiding e. Roditty and Zwick [ICALP 2005] obtained a randomized algorithm with running time of O~(m sqrt{n}). Here we provide the first deterministic algorithm for this problem, with the same O~(m sqrt{n}) time. Due to matching conditional lower bounds of Williams et al. [FOCS 2010], our deterministic combinatorial algorithm for the replacement paths problem is optimal up to polylogarithmic factors (unless the long standing bound of O~(mn) for the combinatorial boolean matrix multiplication can be improved). This also implies a deterministic algorithm for the second simple shortest path problem in O~(m sqrt{n}) time, and a deterministic algorithm for the k-simple shortest paths problem in O~(k m sqrt{n}) time (for any integer constant k > 0). For the problem of distance sensitivity oracles, let G = (V,E) be a directed graph with real-edge weights. An f-Sensitivity Distance Oracle (f-DSO) gets as input the graph G=(V,E) and a parameter f, preprocesses it into a data-structure, such that given a query (s,t,F) with s,t in V and F subseteq E cup V, |F| <=f being a set of at most f edges or vertices (failures), the query algorithm efficiently computes the distance from s to t in the graph G \ F (i.e., the distance from s to t in the graph G after removing from it the failing edges and vertices F). For weighted graphs with real edge weights, Weimann and Yuster [FOCS 2010] presented several randomized f-DSOs. In particular, they presented a combinatorial f-DSO with O~(mn^{4-alpha}) preprocessing time and subquadratic O~(n^{2-2(1-alpha)/f}) query time, giving a tradeoff between preprocessing and query time for every value of 0 < alpha < 1. We derandomize this result and present a combinatorial deterministic f-DSO with the same asymptotic preprocessing and query time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Dynamic graph algorithms
Keywords
  • replacement paths
  • distance sensitivity oracles
  • derandomization

Metrics

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

Related Versions

References

  1. Udit Agarwal, Vijaya Ramachandran, Valerie King, and Matteo Pontecorvi. A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in Õ(n 3/2 ) Rounds. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018, pages 199-205, 2018. Google Scholar
  2. N. Alon and J.H. Spencer. The Probabilistic Method. Fourth Edition. Wiley, 2016. Google Scholar
  3. Noga Alon, Shiri Chechik, and Sarel Cohen. Deterministic combinatorial replacement paths and distance sensitivity oracles. CoRR, abs/1905.07483, 2019. URL: http://arxiv.org/abs/1905.07483.
  4. Grey Ballard, James Demmel, Olga Holtz, and Oded Schwartz. Graph Expansion and Communication Costs of Fast Matrix Multiplication. J. ACM, 59(6):32:1-32:23, January 2013. URL: http://dx.doi.org/10.1145/2395116.2395121.
  5. Austin R. Benson and Grey Ballard. A Framework for Practical Parallel Fast Matrix Multiplication. SIGPLAN Not., 50(8):42-53, January 2015. URL: http://dx.doi.org/10.1145/2858788.2688513.
  6. Aaron Bernstein. A Nearly Optimal Algorithm for Approximating Replacement Paths and K Shortest Simple Paths in General Graphs. In Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '10, pages 742-755, 2010. URL: http://dl.acm.org/citation.cfm?id=1873601.1873662.
  7. Aaron Bernstein and David Karger. Improved Distance Sensitivity Oracles via Random Sampling. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 34-43, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347087.
  8. Aaron Bernstein and David Karger. A Nearly Optimal Oracle for Avoiding Failed Vertices and Edges. In Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing (STOC), pages 101-110, 2009. URL: http://dx.doi.org/10.1145/1536414.1536431.
  9. Shiri Chechik, Sarel Cohen, Amos Fiat, and Haim Kaplan. (1 + ε) approximate f-sensitive Distance Oracles. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '17, pages 1479-1496, 2017. URL: http://dl.acm.org/citation.cfm?id=3039686.3039782.
  10. Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. f-Sensitivity Distance Oracles and Routing Schemes. Algorithmica, 63(4):861-882, 2012. URL: http://dx.doi.org/10.1007/s00453-011-9543-0.
  11. Camil Demetrescu and Mikkel Thorup. Oracles for Distances Avoiding a Link-failure. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 838-843, 2002. URL: http://dl.acm.org/citation.cfm?id=545381.545490.
  12. Camil Demetrescu, Mikkel Thorup, Rezaul Alam Chowdhury, and Vijaya Ramachandran. Oracles for Distances Avoiding a Failed Node or Link. SIAM J. Comput., 37(5):1299-1318, January 2008. URL: http://dx.doi.org/10.1137/S0097539705429847.
  13. Ran Duan and Seth Pettie. Dual-failure Distance and Connectivity Oracles. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 506-515, 2009. URL: http://dl.acm.org/citation.cfm?id=1496770.1496826.
  14. Yuval Emek, David Peleg, and Liam Roditty. A Near-linear-time Algorithm for Computing Replacement Paths in Planar Directed Graphs. ACM Trans. Algorithms, 6(4):64:1-64:13, September 2010. Appeared also in the Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '08). URL: http://dx.doi.org/10.1145/1824777.1824784.
  15. David Eppstein. Finding the k Shortest Paths. SIAM J. Comput., 28(2):652-673, 1998. URL: http://dx.doi.org/10.1137/S0097539795290477.
  16. Zvi Gotthilf and Moshe Lewenstein. Improved Algorithms for the K Simple Shortest Paths and the Replacement Paths Problems. Inf. Process. Lett., 109(7):352-355, March 2009. URL: http://dx.doi.org/10.1016/j.ipl.2008.12.015.
  17. Fabrizio Grandoni and Virginia Vassilevska Williams. Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, 20-23, 2012, pages 748-757, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.17.
  18. J. Huang, L. Rice, D. A. Matthews, and R. A. v. d. Geijn. Generating Families of Practical Fast Matrix Multiplication Algorithms. In 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 656-667, May 2017. URL: http://dx.doi.org/10.1109/IPDPS.2017.56.
  19. Neelesh Khanna and Surender Baswana. Approximate Shortest Paths Avoiding a Failed Vertex: Optimal Size Data Structures for Unweighted Graphs. In 27th International Symposium on Theoretical Aspects of Computer Science, STACS, pages 513-524, 2010. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2010.2481.
  20. 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: http://dx.doi.org/10.1109/SFFCS.1999.814580.
  21. 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: http://dx.doi.org/10.1145/1721837.1721846.
  22. Eugene L. Lawler. A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem. Management Science, 18(7):401-405, 1972. URL: http://dx.doi.org/10.1287/mnsc.18.7.401.
  23. Cheng-Wei Lee and Hsueh-I Lu. Replacement Paths via Row Minima of Concise Matrices. SIAM J. Discrete Math., 28(1):206-225, 2014. URL: http://dx.doi.org/10.1137/120897146.
  24. 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: http://dx.doi.org/10.1016/0167-6377(89)90065-5.
  25. 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: http://dx.doi.org/10.1016/S0020-0190(00)00175-7.
  26. Liam Roditty and Uri Zwick. Replacement Paths and k Simple Shortest Paths in Unweighted Directed Graphs. In Automata, Languages and Programming, 32nd International Colloquium, ICALP, 2005, pages 249-260. See also ACM Trans. Algorithms, 8(4):33:1-11, 2012, 2005. URL: http://dx.doi.org/10.1007/11523468_21.
  27. Oren Weimann and Raphael Yuster. Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication. In Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS '10, pages 655-662, Washington, DC, USA, 2010. IEEE Computer Society. URL: http://dx.doi.org/10.1109/FOCS.2010.68.
  28. Virginia Vassilevska Williams. Faster Replacement Paths. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, 23-25, 2011, pages 1337-1346, 2011. URL: http://dx.doi.org/10.1137/1.9781611973082.102.
  29. Virginia Vassilevska Williams and Ryan Williams. Subcubic Equivalences between Path, Matrix and Triangle Problems. In 51st Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, pages 645-654, 2010. URL: http://dx.doi.org/10.1109/FOCS.2010.67.
  30. Jin Y. Yen. Finding the K Shortest Loopless Paths in a Network. Management Science, 17(11):712-716, 1971. URL: http://dx.doi.org/10.1287/mnsc.17.11.712.
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