research-article

Open access

Approximate Distance Sensitivity Oracles in Subquadratic Space

Authors:

Keerti Choudhary,

Tobias Friedrich,

Simon Krogmann,

Martin SchirneckAuthors Info & Claims

STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing

Pages 1396 - 1409

https://doi.org/10.1145/3564246.3585251

Published: 02 June 2023 Publication History

Abstract

An f-edge fault-tolerant distance sensitive oracle (f-DSO) with stretch σ ≥ 1 is a data structure that preprocesses a given undirected, unweighted graph G with n vertices and m edges, and a positive integer f. When queried with a pair of vertices s, t and a set F of at most f edges, it returns a σ-approximation of the s-t-distance in G−F.

We study f-DSOs that take subquadratic space. Thorup and Zwick [JACM ‍2015] showed that this is only possible for σ ≥ 3. We present, for any constant f ≥ 1 and α ∈ (0, 1/2), and any ε > 0, an f-DSO with stretch 3 + that takes O(n^2−α/f+1/ε) · O(logn/ε)^f+1 space and has an O(n^α/ε²) query time.

We also give an improved construction for graphs with diameter at most D. For any constant k, we devise an f-DSO with stretch 2k−1 that takes O(D^f+o(1) n^1+1/k) space and has O(D^o(1)) query time, with a preprocessing time of O(D^f+o(1) mn^1/k).

Chechik, Cohen, Fiat, and Kaplan [SODA 2017] presented an f-DSO with stretch 1+ and preprocessing time O(n⁵) · O(logn/ε)^f, albeit with a super-quadratic space requirement. We show how to reduce their preprocessing time to O(mn²) · O(logn/ε)^f.

References

[1]

Yehuda Afek, Anat Bremler-Barr, Haim Kaplan, Edith Cohen, and Michael Merritt. 2002. Restoration by Path Concatenation: Fast Recovery of MPLS Paths. Distributed Computing, 15 (2002), 273–283. https://doi.org/10.1007/s00446-002-0080-6

[2]

Noga Alon, Shiri Chechik, and Sarel Cohen. 2019. Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, (ICALP). 12:1–12:14. https://doi.org/10.4230/LIPIcs.ICALP.2019.12

[3]

Surender Baswana and Neelesh Khanna. 2013. Approximate Shortest Paths Avoiding a Failed Vertex: Near Optimal Data Structures for Undirected Unweighted Graphs. Algorithmica, 66 (2013), 18–50. https://doi.org/10.1007/s00453-012-9621-y

[4]

Michael A. Bender and Martín Farach-Colton. 2000. The LCA Problem Revisited. In Proceedings of the 4th Latin American Symposium Theoretical Informatics (LATIN). 88–94. https://doi.org/10.1007/10719839_9

[5]

Aaron Bernstein and David R. Karger. 2008. Improved Distance Sensitivity Oracles via Random Sampling. In Proceedings of the 19th Symposium on Discrete Algorithms (SODA). 34–43. https://dl.acm.org/doi/abs/10.5555/1347082.1347087

[6]

Aaron Bernstein and David R. Karger. 2009. A Nearly Optimal Oracle for Avoiding Failed Vertices and Edges. In Proceedings of the 41st Symposium on Theory of Computing (STOC). 101–110. https://doi.org/10.1145/1536414.1536431

Digital Library

[7]

Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. 2022. Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances. In Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP). 22:1–22:19. https://doi.org/10.4230/LIPIcs.ICALP.2022.22

[8]

Davide Bilò, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. 2021. Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles. In Proceedings of the 29th European Symposium on Algorithms (ESA). 18:1–18:17. https://doi.org/10.4230/LIPIcs.ESA.2021.18

[9]

Davide Bilò, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. 2021. Space-Efficient Fault-Tolerant Diameter Oracles. In Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science (MFCS). 18:1–18:16. https://doi.org/10.4230/LIPIcs.MFCS.2021.18

[10]

Greg Bodwin, Michael Dinitz, and Caleb Robelle. 2021. Optimal Vertex Fault-Tolerant Spanners in Polynomial Time. In Proceedings of the 32nd Symposium on Discrete Algorithms (SODA). 2924–2938. https://doi.org/10.1137/1.9781611976465.174

[11]

Greg Bodwin, Michael Dinitz, and Caleb Robelle. 2022. Partially Optimal Edge Fault-Tolerant Spanners. In Proceedings of the 33rd Symposium on Discrete Algorithms (SODA). 3272–3286. https://doi.org/10.1137/1.9781611977073.129

[12]

Sergio Cabello, Erin W. Chambers, and Jeff Erickson. 2013. Multiple-Source Shortest Paths in Embedded Graphs. SIAM J. Comput., 42 (2013), 1542–1571. https://doi.org/10.1137/120864271

Digital Library

[13]

Shiri Chechik and Sarel Cohen. 2020. Distance Sensitivity Oracles with Subcubic Preprocessing Time and Fast Query Time. In Proccedings of the 52nd Symposium on Theory of Computing (STOC). 1375–1388. https://doi.org/10.1145/3357713.3384253

Digital Library

[14]

Shiri Chechik, Sarel Cohen, Amos Fiat, and Haim Kaplan. 2017. (1+ε )-Approximate f-Sensitive Distance Oracles. In Proceedings of the 28th Symposium on Discrete Algorithms (SODA). 1479–1496. https://doi.org/10.1137/1.9781611974782.96

[15]

Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. 2010. Fault Tolerant Spanners for General Graphs. SIAM J. Comput., 39 (2010), 3403–3423. https://doi.org/10.1137/090758039

Digital Library

[16]

Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. 2012. f-Sensitivity Distance Oracles and Routing Schemes. Algorithmica, 63 (2012), 861–882. https://doi.org/10.1007/s00453-011-9543-0

[17]

Camil Demetrescu and Mikkel Thorup. 2002. Oracles for Distances Avoiding a Link-Failure. In Proceedings of the 13th Symposium on Discrete Algorithms (SODA). 838–843. https://dl.acm.org/doi/10.5555/545381.545490

[18]

Camil Demetrescu, Mikkel Thorup, Rezaul A. Chowdhury, and Vijaya Ramachandran. 2008. Oracles for Distances Avoiding a Failed Node or Link. SIAM J. Comput., 37 (2008), 1299–1318. https://doi.org/10.1137/S0097539705429847

Digital Library

[19]

Ran Duan and Seth Pettie. 2009. Dual-Failure Distance and Connectivity Oracles. In Proceedings of the 20th Symposium on Discrete Algorithms (SODA). 506–515. https://dl.acm.org/doi/10.5555/545381.545490

[20]

Ran Duan and Hanlin Ren. 2022. Maintaining Exact Distances under Multiple Edge Failures. In Proceedings of the 54th Symposium on Theory of Computing (STOC). 1093–1101. https://doi.org/10.1145/3519935.3520002

Digital Library

[21]

Paul Erdős. 1964. Extremal Problems in Graph Theory. Theory of Graphs and its Applications, 29–36.

[22]

Fabrizio Grandoni and Virginia Vassilevska Williams. 2020. Faster Replacement Paths and Distance Sensitivity Oracles. ACM Transaction on Algorithms, 16 (2020), 15:1–15:25. https://doi.org/10.1145/3365835

Digital Library

[23]

Yong Gu and Hanlin Ren. 2021. Constructing a Distance Sensitivity Oracle in O(n^2.5794M) Time. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP). 76:1–76:20. https://doi.org/10.4230/LIPIcs.ICALP.2021.76

[24]

Torben Hagerup, Peter Bro Miltersen, and Rasmus Pagh. 2001. Deterministic Dictionaries. Journal of Algorithms, 41 (2001), 69–85. https://doi.org/10.1006/jagm.2001.1171

Digital Library

[25]

Karthik C.S. and Merav Parter. 2021. Deterministic Replacement Path Covering. In Proceedings of the 32nd Symposium on Discrete Algorithms (SODA). 704–723. https://doi.org/10.1137/1.9781611976465.44

[26]

Christos Levcopoulos, Giri Narasimhan, and Michiel H. M. Smid. 1998. Efficient Algorithms for Constructing Fault-Tolerant Geometric Spanners. In Proceedings of the 30th Symposium on Theory of Computing (STOC). 186–195. https://doi.org/10.1145/276698.276734

Digital Library

[27]

Hanlin Ren. 2022. Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time. J. Comput. System Sci., 123 (2022), 159–170. https://doi.org/10.1016/j.jcss.2021.08.005

Digital Library

[28]

Liam Roditty and Uri Zwick. 2012. Replacement Paths and k Simple Shortest Paths in Unweighted Directed Graphs. ACM Transaction on Algorithms, 8 (2012), Article 33, 33:1–33:11 pages. https://doi.org/10.1145/2344422.2344423

Digital Library

[29]

Mikkel Thorup and Uri Zwick. 2005. Approximate Distance Oracles. J. ACM, 52 (2005), 1–24. https://doi.org/10.1145/1044731.1044732

Digital Library

[30]

Oren Weimann and Raphael Yuster. 2013. Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication. ACM Transactions on Algorithms, 9 (2013), 14:1–14:13. https://doi.org/10.1145/2438645.2438646

Digital Library

Cited By

Index Terms

Approximate Distance Sensitivity Oracles in Subquadratic Space
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
    2. Graph algorithms analysis
      1. Shortest paths

Recommendations

Compact Distance Oracles with Large Sensitivity and Low Stretch
Algorithms and Data Structures
Abstract
An f-edge fault-tolerant distance sensitive oracle (f-DSO) with stretch $σ ⩾ 1$ is a data structure that preprocesses an input graph G. When queried with the triple (s, t, F), where $s, t \in V$ and $F \subseteq E$ contains at most f edges of G, the oracle returns an ... ${\overset{}{}}_{}$ $_{}$ $_{} {\overset{}{}}_{}_{}$
$^{\frac{}{}}$ $\overset{}{}^{\frac{}{} \frac{}{}}$
$^{}$ $^{}$ $^{\frac{}{}}$
Approximate distance oracles with improved stretch for sparse graphs
Abstract
Thorup and Zwick [1] introduced the notion of approximate distance oracles, a data structure that produces for an n-vertex, m-edge weighted undirected graph G = ( V , E ), distance estimations in constant query time. They presented a ...
Highlights
- Graph sparsity can help to get space-stretch tradeoffs for Distance Oracle which are strictly better than Thorup and Zwick space-stretch tradeoffs for ...
Approximate Distance Oracles with Improved Stretch for Sparse Graphs
Computing and Combinatorics
Abstract
Thorup and Zwick [19] introduced the notion of approximate distance oracles, a data structure that produces for an n-vertices, m-edges weighted undirected graph $G = (V, E)$ , distance estimations in constant query time. They presented a distance oracle ... $^{}$
$\overset{}{}$ $\overset{}{}^{}$ $\overset{}{}$
$\overset{}{}^{}$ $^{}$ $^{}$ $^{}$ $^{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing

June 2023

1926 pages

ISBN:9781450399135

DOI:10.1145/3564246

General Chair:
Barna Saha
University of California at San Diego, USA
,
Program Chair:
Rocco A. Servedio
Columbia University, USA

Copyright © 2023 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 June 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

European Research Council

Conference

STOC '23

Sponsor:

SIGACT

STOC '23: 55th Annual ACM Symposium on Theory of Computing

June 20 - 23, 2023

FL, Orlando, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
203
Total Downloads

Downloads (Last 12 months)164
Downloads (Last 6 weeks)34

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents