Document Open Access Logo

Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances

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

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.22.pdf
  • Filesize: 0.84 MB
  • 19 pages

Document Identifiers

Author Details

Davide Bilò
  • Department of Information Engineering, Computer Science and Mathematics, University of L'Aquila, Italy
Keerti Choudhary
  • Department of Computer Science and Engineering, Indian Institute of Technology Delhi, India
Sarel Cohen
  • School of Computer Science, The Academic College of Tel Aviv-Yaffo, Israel
Tobias Friedrich
  • Hasso Plattner Institute, University of Potsdam, Germany
Martin Schirneck
  • Hasso Plattner Institute, University of Potsdam, Germany

Cite As Get BibTex

Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 22:1-22:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ICALP.2022.22

Abstract

We construct data structures for extremal and pairwise distances in directed graphs in the presence of transient edge failures. Henzinger et al. [ITCS 2017] initiated the study of fault-tolerant (sensitivity) oracles for the diameter and vertex eccentricities. We extend this with a special focus on space efficiency. We present several new data structures, among them the first fault-tolerant eccentricity oracle for dual failures in subcubic space. We further prove lower bounds that show limits to approximation vs. space and diameter vs. space trade-offs for fault-tolerant oracles. They highlight key differences between data structures for undirected and directed graphs.
Initially, our oracles are randomized leaning on a sampling technique frequently used in sensitivity analysis. Building on the work of Alon, Chechik, and Cohen [ICALP 2019] as well as Karthik and Parter [SODA 2021], we develop a hierarchical framework to derandomize fault-tolerant data structures. We first apply it to our own diameter and eccentricity oracles and then show its versatility by derandomizing algorithms from the literature: the distance sensitivity oracle of Ren [JCSS 2022] and the Single-Source Replacement Path algorithm of Chechik and Magen [ICALP 2020]. This way, we obtain the first deterministic distance sensitivity oracle with subcubic preprocessing time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
  • Theory of computation → Pseudorandomness and derandomization
  • Mathematics of computing → Graph algorithms
Keywords
  • derandomization
  • diameter
  • eccentricity
  • fault-tolerant data structure
  • sensitivity oracle
  • space lower bound

Metrics

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

Related Versions

References

  1. 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.
  2. 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.
  3. Surender Baswana, Keerti Choudhary, and Liam Roditty. Fault-tolerant subgraph for single-source reachability: General and optimal. SIAM Journal on Computing, 47:80-95, 2018. URL: https://doi.org/10.1137/16M1087643.
  4. 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.
  5. Davide Bilò, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles. In Proceedings of the 29th European Symposium on Algorithms (ESA), pages 18:1-18:17, 2021. URL: https://doi.org/10.4230/LIPIcs.ESA.2021.18.
  6. Davide Bilò, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. Space-Efficient Fault-Tolerant Diameter Oracles. In Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 18:1-18:16, 2021. URL: https://doi.org/10.4230/LIPIcs.MFCS.2021.18.
  7. Greg Bodwin. Linear Size Distance Preservers. In Proceedings of the 28th Symposium on Discrete Algorithms (SODA), pages 600-615, 2017. URL: http://dl.acm.org/citation.cfm?id=3039686.3039725.
  8. Jan van den Brand and Thatchaphol Saranurak. Sensitive Distance and Reachability Oracles for Large Batch Updates. In Proceedings of the 60th Symposium on Foundations of Computer Science (FOCS), pages 424-435, 2019. URL: https://doi.org/10.1109/FOCS.2019.00034.
  9. Shiri Chechik and Sarel Cohen. Near Optimal Algorithms for the Single Source Replacement Paths Problem. In Proceedings of the 30th Symposium on Discrete Algorithms (SODA), pages 2090-2109, 2019. URL: https://doi.org/10.1137/1.9781611975482.126.
  10. 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.
  11. Shiri Chechik, Sarel Cohen, Amos Fiat, and Haim Kaplan. (1+ε)-Approximate f-Sensitive Distance Oracles. In Proceedings of the 28th Symposium on Discrete Algorithms (SODA), pages 1479-1496, 2017. URL: https://doi.org/10.1137/1.9781611974782.96.
  12. 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.
  13. 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.
  14. Ran Duan, Yong Gu, and Hanlin Ren. Approximate Distance Oracles Subject to Multiple Vertex Failures. In Proceedings of the 32nd Symposium on Discrete Algorithms (SODA), pages 2497-2516, 2021. URL: https://doi.org/10.1137/1.9781611976465.148.
  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 Seth Pettie. Fast Algorithms for (max,min)-Matrix Multiplication and Bottleneck Shortest Paths. In Proceedings of the 20th Symposium on Discrete Algorithms (SODA), pages 384-391, 2009. URL: http://dl.acm.org/citation.cfm?id=1496770.1496813.
  17. Ran Duan and Hanlin Ren. Maintaining Exact Distances under Multiple Edge Failures. In Proceedings of the 54th Symposium on Theory of Computing (STOC), 2022. To appear. Google Scholar
  18. Ran Duan and Tianyi Zhang. Improved Distance Sensitivity Oracles via Tree Partitioning. In Proceedings of the 15th International Symposium on Algorithms and Data Structures (WADS), pages 349-360, 2017. URL: https://doi.org/10.1007/978-3-319-62127-2_30.
  19. François Le Gall and Florent Urrutia. Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor. In Proceedings of the 29th Symposium on Discrete Algorithms (SODA), pages 1029-1046, 2018. URL: https://doi.org/10.1137/1.9781611975031.67.
  20. François Le Gall. Faster Algorithms for Rectangular Matrix Multiplication. In Proceedings of the 53rd Symposium on Foundations of Computer Science (FOCS), pages 514-523, 2012. URL: https://doi.org/10.1109/FOCS.2012.80.
  21. 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.
  22. 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.
  23. 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), pages 76:1-76:20, 2021. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.76.
  24. 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.
  25. Torben Hagerup, Peter Bro Miltersen, and Rasmus Pagh. Deterministic Dictionaries. Journal of Algorithms, 41:69-85, 2001. URL: https://doi.org/10.1006/jagm.2001.1171.
  26. Monika Henzinger, Andrea Lincoln, Stefan Neumann, and Virginia Vassilevska Williams. Conditional Hardness for Sensitivity Problems. In Proceedings of the 8th Conference on Innovations in Theoretical Computer Science (ITCS), pages 26:1-26:31, 2017. URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.26.
  27. Giuseppe F. Italiano, Luigi Laura, and Federico Santaroni. Finding Strong Bridges and Strong Articulation Points in Linear Time. Theoretical Computer Science, 447:74-84, 2012. URL: https://doi.org/10.1016/j.tcs.2011.11.011.
  28. Karthik C.S. and Merav Parter. Deterministic Replacement Path Covering. In Proceedings of the 32nd Symposium on Discrete Algorithms (SODA), pages 704-723, 2021. URL: https://doi.org/10.1137/1.9781611976465.44.
  29. Valerie King. Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs. In Proceedings of the 40th Symposium on Foundations of Computer Science (FOCS), pages 81-91, 1999. URL: https://doi.org/10.1109/SFFCS.1999.814580.
  30. Grazia Lotti and Francesco Romani. On the Asymptotic Complexity of Rectangular Matrix Multiplication. Theoretical Computer Science, 23:171-185, 1983. URL: https://doi.org/10.1016/0304-3975(83)90054-3.
  31. 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.
  32. Hanlin Ren. Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time. Journal of Computer and System Sciences, 123:159-170, 2022. Journal version of [Hanlin Ren, 2020]. URL: https://doi.org/10.1016/j.jcss.2021.08.005.
  33. 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.
  34. Avi Shoshan and Uri Zwick. All Pairs Shortest Paths in Undirected Graphs with Integer Weights. In Proceedings of the 40th Symposium on Foundations of Computer Science (FOCS), pages 605-615, 1999. URL: https://doi.org/10.1109/SFFCS.1999.814635.
  35. 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.
  36. Uri Zwick. All Pairs Shortest Paths Using Bridging Sets and Rectangular Matrix Multiplication. Journal of the ACM, 49: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