Document Open Access Logo

Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time

Author Hanlin Ren

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.79.pdf
  • Filesize: 0.57 MB
  • 13 pages

Document Identifiers

Author Details

Hanlin Ren
  • Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China

Acknowledgements

I would like to thank Zihao Li for introducing this problem to me, and Ran Duan and Yong Gu for helpful discussions. I would also like to thank Hongxun Wu for reading and commenting an early draft version of this paper, and pointing out the issue with non-unique shortest paths. I am also grateful to the anonymous referees of ESA for their helpful comments that improves the presentation of this work.

Cite As Get BibTex

Hanlin Ren. Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 79:1-79:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ESA.2020.79

Abstract

We consider the problem of building Distance Sensitivity Oracles (DSOs). Given a directed graph G = (V, E) with edge weights in {1, 2, … , M}, we need to preprocess it into a data structure, and answer the following queries: given vertices u,v,x ∈ V, output the length of the shortest path from u to v that does not go through x. Our main result is a simple DSO with Õ(n^2.7233 M²) preprocessing time and O(1) query time. Moreover, if the input graph is undirected, the preprocessing time can be improved to Õ(n^2.6865 M²). Our algorithms are randomized with correct probability ≥ 1-1/n^c, for a constant c that can be made arbitrarily large. Previously, there is a DSO with Õ(n^2.8729 M) preprocessing time and polylog(n) query time [Chechik and Cohen, STOC'20].
At the core of our DSO is the following observation from [Bernstein and Karger, STOC'09]: if there is a DSO with preprocessing time P and query time Q, then we can construct a DSO with preprocessing time P+Õ(Mn²)⋅ Q and query time O(1). (Here Õ(⋅) hides polylog(n) factors.)

Subject Classification

ACM Subject Classification
  • Theory of computation → Shortest paths
  • Theory of computation → Data structures design and analysis
Keywords
  • Graph theory
  • Failure-prone structures

Metrics

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

Related Versions

References

  1. Michael A. Bender and Martin Farach-Colton. The LCA problem revisited. In Gaston H. Gonnet, Daniel Panario, and Alfredo Viola, editors, LATIN 2000: Theoretical Informatics, 4th Latin American Symposium, Punta del Este, Uruguay, April 10-14, 2000, Proceedings, volume 1776 of Lecture Notes in Computer Science, pages 88-94. Springer, 2000. URL: https://doi.org/10.1007/10719839_9.
  2. Aaron Bernstein and David R. Karger. Improved distance sensitivity oracles via random sampling. In Shang-Hua Teng, editor, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008, pages 34-43. SIAM, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347087.
  3. Aaron Bernstein and David R. Karger. A nearly optimal oracle for avoiding failed vertices and edges. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 101-110. ACM, 2009. URL: https://doi.org/10.1145/1536414.1536431.
  4. Shiri Chechik and Sarel Cohen. Distance sensitivity oracles with subcubic preprocessing time and fast query time. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1375-1388. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384253.
  5. Erik D. Demaine, Gad M. Landau, and Oren Weimann. On Cartesian trees and range minimum queries. Algorithmica, 68(3):610-625, 2014. URL: https://doi.org/10.1007/s00453-012-9683-x.
  6. 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, 2008. URL: https://doi.org/10.1137/S0097539705429847.
  7. Ran Duan and Seth Pettie. Dual-failure distance and connectivity oracles. In Claire Mathieu, editor, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, pages 506-515. SIAM, 2009. URL: http://dl.acm.org/citation.cfm?id=1496770.1496826.
  8. Ran Duan and Tianyi Zhang. Improved distance sensitivity oracles via tree partitioning. In Faith Ellen, Antonina Kolokolova, and Jörg-Rüdiger Sack, editors, Algorithms and Data Structures - 15th International Symposium, WADS 2017, St. John’s, NL, Canada, July 31 - August 2, 2017, Proceedings, volume 10389 of Lecture Notes in Computer Science, pages 349-360. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-62127-2_30.
  9. Michael L. Fredman, János Komlós, and Endre Szemerédi. Storing a sparse table with O(1) worst case access time. In 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982, pages 165-169. IEEE Computer Society, 1982. URL: https://doi.org/10.1109/SFCS.1982.39.
  10. François Le Gall. Powers of tensors and fast matrix multiplication. In Katsusuke Nabeshima, Kosaku Nagasaka, Franz Winkler, and Ágnes Szántó, editors, International Symposium on Symbolic and Algebraic Computation, ISSAC '14, Kobe, Japan, July 23-25, 2014, pages 296-303. ACM, 2014. URL: https://doi.org/10.1145/2608628.2608664.
  11. Francois Le Gall and Florent Urrutia. Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1029-1046. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.67.
  12. 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, New Brunswick, NJ, USA, October 20-23, 2012, pages 748-757. IEEE Computer Society, 2012. URL: https://doi.org/10.1109/FOCS.2012.17.
  13. Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams. Tight hardness for shortest cycles and paths in sparse graphs. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1236-1252. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.80.
  14. Grazia Lotti and Francesco Romani. On the asymptotic complexity of rectangular matrix multiplication. Theor. Comput. Sci., 23:171-185, 1983. URL: https://doi.org/10.1016/0304-3975(83)90054-3.
  15. Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani. Matching is as easy as matrix inversion. Combinatorica, 7(1):105-113, 1987. URL: https://doi.org/10.1007/BF02579206.
  16. Raimund Seidel. On the all-pairs-shortest-path problem in unweighted undirected graphs. J. Comput. Syst. Sci., 51(3):400-403, 1995. URL: https://doi.org/10.1006/jcss.1995.1078.
  17. Avi Shoshan and Uri Zwick. All pairs shortest paths in undirected graphs with integer weights. In 40th Annual Symposium on Foundations of Computer Science, FOCS '99, 17-18 October, 1999, New York, NY, USA, pages 605-615. IEEE Computer Society, 1999. URL: https://doi.org/10.1109/SFFCS.1999.814635.
  18. Noam Ta-Shma. A simple proof of the isolation lemma. Electronic Colloquium on Computational Complexity (ECCC), 22:80, 2015. URL: https://eccc.weizmann.ac.il/report/2015/080.
  19. Oren Weimann and Raphael Yuster. Replacement paths and distance sensitivity oracles via fast matrix multiplication. ACM Trans. Algorithms, 9(2):14:1-14:13, 2013. URL: https://doi.org/10.1145/2438645.2438646.
  20. Uri Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM, 49(3):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