Document Open Access Logo

Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles

Authors Davide Bilò , Sarel Cohen, Tobias Friedrich , Martin Schirneck

PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.18.pdf
  • Filesize: 0.83 MB
  • 17 pages

Document Identifiers

Author Details

Davide Bilò
  • Department of Humanities and Social Sciences, University of Sassari, Italy
Sarel Cohen
  • Hasso Plattner Institute, University of Potsdam, Germany
Tobias Friedrich
  • Hasso Plattner Institute, University of Potsdam, Germany
Martin Schirneck
  • Hasso Plattner Institute, University of Potsdam, Germany

Funding

  • Bilò, Davide: This work was partially supported by the Research Grant FBS2016_BILO, funded by "Fondazione di Sardegna" in 2016.

Cite AsGet BibTex

Davide Bilò, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ESA.2021.18

Abstract

Given a graph with a distinguished source vertex s, the Single Source Replacement Paths (SSRP) problem is to compute and output, for any target vertex t and edge e, the length d(s,t,e) of a shortest path from s to t that avoids a failing edge e. A Single-Source Distance Sensitivity Oracle (Single-Source DSO) is a compact data structure that answers queries of the form (t,e) by returning the distance d(s,t,e). We show how to deterministically compress the output of the SSRP problem on n-vertex, m-edge graphs with integer edge weights in the range [1,M] into a Single-Source DSO that has size O(M^{1/2} n^{3/2}) and query time Õ(1). We prove that the space requirement is optimal (up to the word size). Our techniques can also handle vertex failures within the same bounds. Chechik and Cohen [SODA 2019] presented a combinatorial, randomized Õ(m√n+n²) time SSRP algorithm for undirected and unweighted graphs. We derandomize their algorithm with the same asymptotic running time and apply our compression to obtain a deterministic Single-Source DSO with Õ(m√n+n²) preprocessing time, O(n^{3/2}) space, and Õ(1) query time. Our combinatorial Single-Source DSO has near-optimal space, preprocessing and query time for unweighted graphs, improving the preprocessing time by a √n-factor compared to previous results with o(n²) space. Grandoni and Vassilevska Williams [FOCS 2012, TALG 2020] gave an algebraic, randomized Õ(Mn^ω) time SSRP algorithm for (undirected and directed) graphs with integer edge weights in the range [1,M], where ω < 2.373 is the matrix multiplication exponent. We derandomize it for undirected graphs and apply our compression to obtain an algebraic Single-Source DSO with Õ(Mn^ω) preprocessing time, O(M^{1/2} n^{3/2}) space, and Õ(1) query time. This improves the preprocessing time of algebraic Single-Source DSOs by polynomial factors compared to previous o(n²)-space oracles. We also present further improvements of our Single-Source DSOs. We show that the query time can be reduced to a constant at the cost of increasing the size of the oracle to O(M^{1/3} n^{5/3}) and that all our oracles can be made path-reporting. On sparse graphs with m = O(n^{5/4-ε}/M^{7/4}) edges, for any constant ε > 0, we reduce the preprocessing to randomized Õ(M^{7/8} m^{1/2} n^{11/8}) = O(n^{2-ε/2}) time. To the best of our knowledge, this is the first truly subquadratic time algorithm for building Single-Source DSOs on sparse graphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Shortest paths
  • Theory of computation → Data structures design and analysis
  • Theory of computation → Cell probe models and lower bounds
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • derandomization
  • distance sensitivity oracle
  • single-source replacement paths
  • space lower bound

Metrics

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

Related Versions

References

  1. Yehuda Afek, Anat Bremler-Barr, Haim Kaplan, Edith Cohen, and Michael Merritt. Restoration by Path Concatenation: Fast Recovery of MPLS Paths. Distributed Computing, 15:273-283, 2002. URL: https://doi.org/10.1007/s00446-002-0080-6.
  2. Josh Alman and Virginia Vassilevska Williams. A Refined Laser Method and Faster Matrix Multiplication. In Proceedings of the 32nd Symposium on Discrete Algorithms (SODA), pages 522-539, 2021. URL: https://doi.org/10.1137/1.9781611976465.32.
  3. Noga Alon, Shiri Chechik, and Sarel Cohen. Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, (ICALP), pages 12:1-12:14, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.12.
  4. Michael A. Bender and Martin Farach-Colton. The LCA Problem Revisited. In Proceedings of the 4th Latin American Symposium Theoretical Informatics (LATIN), pages 88-94, 2000. URL: https://doi.org/10.1007/10719839_9.
  5. Aaron Bernstein and David R. Karger. Improved Distance Sensitivity Oracles via Random Sampling. In Proceedings of the 19th Symposium on Discrete Algorithms (SODA), pages 34-43, 2008. URL: https://dl.acm.org/citation.cfm?id=1347082.1347087.
  6. Aaron Bernstein and David R. Karger. A Nearly Optimal Oracle for Avoiding Failed Vertices and Edges. In Proceedings of the 41st Symposium on Theory of Computing (STOC), pages 101-110, 2009. URL: https://doi.org/10.1145/1536414.1536431.
  7. Davide Bilò, Keerti Choudhary, Luciano Gualà, Stefano Leucci, Merav Parter, and Guido Proietti. Efficient Oracles and Routing Schemes for Replacement Paths. In Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science (STACS), pages 13:1-13:15, 2018. URL: https://doi.org/10.4230/LIPIcs.STACS.2018.13.
  8. Davide Bilò, Luciano Gualà, Stefano Leucci, and Guido Proietti. Fault-Tolerant Approximate Shortest-Path Trees. Algorithmica, 80:3437-3460, 2018. URL: https://doi.org/10.1007/s00453-017-0396-z.
  9. Jan van den Brand and Thatchaphol Saranurak. Sensitive Distance and Reachability Oracles for Large Batch Updates. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS, 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 424-435. IEEE Computer Society, 2019. URL: https://doi.org/10.1109/FOCS.2019.00034.
  10. Shiri Chechik and Sarel Cohen. Near Optimal Algorithms for the Single Source Replacement Paths Problem. In Proceedings of the 30th Annual Symposium on Discrete Algorithms (SODA), pages 2090-2109, 2019. URL: https://doi.org/10.1137/1.9781611975482.126.
  11. Shiri Chechik and Sarel Cohen. Distance Sensitivity Oracles with Subcubic Preprocessing Time and Fast Query Time. In Proccedings of the 52nd Symposium on Theory of Computing (STOC), pages 1375-1388, 2020. URL: https://doi.org/10.1145/3357713.3384253.
  12. Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. f-Sensitivity Distance Oracles and Routing Schemes. Algorithmica, 63:861-882, 2012. URL: https://doi.org/10.1007/s00453-011-9543-0.
  13. Shiri Chechik and Ofer Magen. Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP), pages 81:1-81:17, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.81.
  14. Camil Demetrescu, Mikkel Thorup, Rezaul A. Chowdhury, and Vijaya Ramachandran. Oracles for Distances Avoiding a Failed Node or Link. SIAM Journal on Computing, 37:1299-1318, 2008. URL: https://doi.org/10.1137/S0097539705429847.
  15. Ran Duan and Seth Pettie. Dual-failure Distance and Connectivity Oracles. In Proceedings of the 20th Symposium on Discrete Algorithms (SODA), pages 506-515, 2009. URL: https://dl.acm.org/citation.cfm?id=1496770.1496826.
  16. Ran Duan and Tianyi Zhang. Improved Distance Sensitivity Oracles via Tree Partitioning. In Proceedings of the 15th Algorithms and Data Structures Symposium (WADS), pages 349-360, 2017. URL: https://doi.org/10.1007/978-3-319-62127-2_30.
  17. Fabrizio Grandoni and Virginia Vassilevska Williams. Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths. In Proceedings of the 53rd Symposium on Foundations of Computer Science (FOCS), pages 748-757, 2012. URL: https://doi.org/10.1109/FOCS.2012.17.
  18. Fabrizio Grandoni and Virginia Vassilevska Williams. Faster Replacement Paths and Distance Sensitivity Oracles. ACM Transaction on Algorithms, 16:15:1-15:25, 2020. URL: https://doi.org/10.1145/3365835.
  19. Yong Gu and Hanlin Ren. Constructing a Distance Sensitivity Oracle in O(n^2.5794M) Time. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP), 2021. To appear. Google Scholar
  20. Yuzhou Gu, Adam Polak, Virginia Vassilevska Williams, and Yinzhan Xu. Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP), 2021. To appear. Google Scholar
  21. Manoj Gupta, Rahul Jain, and Nitiksha Modi. Multiple Source Replacement Path Problem. In Proceedings of the 39th Symposium on Principles of Distributed Computing (PODC), pages 339-348, 2020. URL: https://doi.org/10.1145/3382734.3405714.
  22. Manoj Gupta and Aditi Singh. Generic Single Edge Fault Tolerant Exact Distance Oracle. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, (ICALP), pages 72:1-72:15, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.72.
  23. John Hershberger and Subhash Suri. Vickrey Prices and Shortest Paths: What is an edge worth? In Proceedings of the 42nd Symposium on Foundations of Computer Science (FOCS), pages 252-259, 2001. URL: https://doi.org/10.1109/SFCS.2001.959899.
  24. John Hershberger and Subhash Suri. Erratum to "Vickrey Pricing and Shortest Paths: What is an edge worth?". In Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS), page 809, 2002. URL: https://doi.org/10.1109/SFCS.2002.1182006.
  25. François Le Gall. Powers of Tensors and Fast Matrix Multiplication. In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC), pages 296-303, 2014. URL: https://doi.org/10.1145/2608628.2608664.
  26. Kavindra Malik, A. K. Mittal, and Sumit K. Gupta. The k Most Vital Arcs in the Shortest Path Problem. Operations Research Letters, 8:223-227, 1989. URL: https://doi.org/10.1016/0167-6377(89)90065-5.
  27. Enrico Nardelli, Guido Proietti, and Peter Widmayer. A Faster Computation of the Most Vital Edge of a Shortest Path. Information Processing Letters, 79:81-85, 2001. URL: https://doi.org/10.1016/S0020-0190(00)00175-7.
  28. Enrico Nardelli, Guido Proietti, and Peter Widmayer. Finding the Most Vital Node of a Shortest Path. Theoretical Computer Science, 296:167-177, 2003. URL: https://doi.org/10.1016/S0304-3975(02)00438-3.
  29. Merav Parter and David Peleg. Sparse Fault-Tolerant BFS Structures. ACM Transactions on Algorithms, 13:11:1-11:24, 2016. URL: https://doi.org/10.1145/2976741.
  30. Hanlin Ren. Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time. In Proceedings of the 28th European Symposium on Algorithms (ESA), pages 79:1-79:13, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.79.
  31. Hanlin Ren. Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time. CoRR, abs/2007.11495, 2020. ArXiv preprint. Full version of [Hanlin Ren, 2020]. URL: http://arxiv.org/abs/2007.11495.
  32. Liam Roditty and Uri Zwick. Replacement Paths and k Simple Shortest Paths in Unweighted Directed Graphs. ACM Transaction on Algorithms, 8:33:1-33:11, 2012. URL: https://doi.org/10.1145/2344422.2344423.
  33. Mikkel Thorup. Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time. Journal of the ACM, 46:362–394, 1999. URL: https://doi.org/10.1145/316542.316548.
  34. Mikkel Thorup and Uri Zwick. Approximate Distance Oracles. Journal of the ACM, 52:1-24, 2005. URL: https://doi.org/10.1145/1044731.1044732.
  35. Virginia Vassilevska Williams. Multiplying Matrices Faster Than Coppersmith-Winograd. In Proceedings of the 44th Symposium on Theory of Computing (STOC), pages 887-898, 2012. URL: https://doi.org/10.1145/2213977.2214056.
  36. Virginia Vassilevska Williams and R. Ryan Williams. Subcubic Equivalences Between Path, Matrix, and Triangle Problems. Journal of the ACM, 65:27:1-27:38, 2018. URL: https://doi.org/10.1145/3186893.
  37. Oren Weimann and Raphael Yuster. Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication. ACM Transactions on Algorithms, 9:14:1-14:13, 2013. URL: https://doi.org/10.1145/2438645.2438646.
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