Reliable Spanners for Metric Spaces
Article No.: 7, Pages 1 - 27
Abstract
A spanner is reliable if it can withstand large, catastrophic failures in the network. More precisely, any failure of some nodes can only cause a small damage in the remaining graph in terms of the dilation. In other words, the spanner property is maintained for almost all nodes in the residual graph. Constructions of reliable spanners of near linear size are known in the low-dimensional Euclidean settings. Here, we present new constructions of reliable spanners for planar graphs, trees, and (general) metric spaces.
References
[1]
Ittai Abraham and Cyril Gavoille. 2006. Object location using path separators. In Proceedings of the 25th ACM Symposium on Principles of Distributed Computing, Eric Ruppert and Dahlia Malkhi (Eds.). ACM, New York, NY, 188–197.
[2]
Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, and Kunal Talwar. 2019. Cops, robbers, and threatening skeletons: Padded decomposition for minor-free graphs. SIAM J. Comput. 48, 3 (2019), 1120–1145.
[3]
Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, and Udi Wieder. 2010. Strong-diameter decompositions of minor free graphs. Theory Comput. Syst. 47, 4 (2010), 837–855.
[4]
N. Alon and F. R. K. Chung. 1988. Explicit construction of linear sized tolerant networks, In Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986). Discrete Math. 72, 15–19.
[5]
Baruch Awerbuch and David Peleg. 1990. Sparse partitions. In Proceedings of the 31st IEEE Symposium on Foundations of Computer Science (FOCS’90). IEEE Computer Society, USA, 503–513.
[6]
Y. Bartal. 1998. On approximating arbitrary metrics by tree metrics. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing(STOC’98). ACM, New York, NY, 161–168.
[7]
Yair Bartal, Nathan Linial, Manor Mendel, and Assaf Naor. 2005. On metric Ramsey-type phenomena. Ann. Math. 162, 2 (2005), 643–709.
[8]
Greg Bodwin, Michael Dinitz, Merav Parter, and Virginia Vassilevska Williams. 2018. Optimal Vertex Fault Tolerant Spanners (for Fixed Stretch). SIAM, 3600 University City Science Center, Philadelphia, PA, 1884–1900. Retrieved from arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611975031.123
[9]
P. Bose, P. Carmi, V. Dujmovic, and P. Morin. 2018. Near-optimal O(k)-robust geometric spanners. Retrieved from http://arxiv.org/abs/1812.09913.
[10]
P. Bose, V. Dujmović, P. Morin, and M. Smid. 2013. Robust geometric spanners. SIAM J. Comput. 42, 4 (2013), 1720–1736.
[11]
Kevin Buchin, Sariel Har-Peled, and Dániel Oláh. 2019. A spanner for the day after. In Proceedings of the 35th International Symposium on Computational Geometry (SoCG’19) (LIPIcs), Gill Barequet and Yusu Wang (Eds.), Vol. 129. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 19:1–19:15.
[12]
Kevin Buchin, Sariel Har-Peled, and Dániel Oláh. 2020. Sometimes reliable spanners of almost linear size. In Proceedings of the 29th Annual European Symposium on Algorithms (ESA’20) (LIPIcs), Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders (Eds.), Vol. 173. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 27:1–27:15.
[13]
Costas Busch, Ryan LaFortune, and Srikanta Tirthapura. 2014. Sparse covers for planar graphs and graphs that exclude a fixed minor. Algorithmica 69, 3 (2014), 658–684.
[14]
T.-H. H. Chan, M. Li, L. Ning, and S. Solomon. 2015. New doubling spanners: Better and simpler. SIAM J. Comput. 44, 1 (2015), 37–53.
[15]
Ioana Dumitriu, Tobias Johnson, Soumik Pal, and Elliot Paquette. 2013. Functional limit theorems for random regular graphs. Prob. Theory Related Fields 156, 3–4 (2013), 921–975.
[16]
J. Fakcharoenphol, S. Rao, and K. Talwar. 2004. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Sys. Sci. 69, 3 (2004), 485–497.
[17]
Arnold Filtser and Hung Le. 2021. Reliable spanners: Locality-sensitive orderings strike back. Retrieved from https://arxiv.org/abs/2101.07428.
[18]
Joel Friedman. 2003. A proof of Alon’s second eigenvalue conjecture. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing(STOC’03), Lawrence L. Larmore and Michel X. Goemans (Eds.). ACM, New York, NY, 720–724.
[19]
Joel Friedman, Jeff Kahn, and Endre Szemerédi. 1989. On the second eigenvalue in random regular graphs. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, David S. Johnson (Ed.). ACM, New York, NY, 587–598.
[20]
Sariel Har-Peled, Manor Mendel, and Dániel Oláh. 2021. Reliable spanners for metric spaces. In Proceedings of the 37th International Annual Symposium on Computational Geometry(SoCG’21) (LIPIcs), Kevin Buchin and Éric Colin de Verdière (Eds.), Vol. 189. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 43:1–43:13.
[21]
Shlomo Hoory, Nathan Linial, and Avi Wigderson. 2006. Expander graphs and their applications. Bull. Amer. Math. Soc. (N.S.) 43, 4 (2006), 439–561.
[22]
R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor. 2005. Measured descent: A new embedding method for finite metric spaces. Geom. Funct. Anal. 15, 4 (2005), 839–858.
[23]
C. Levcopoulos, G. Narasimhan, and M. Smid. 2002. Improved algorithms for constructing fault-tolerant spanners. Algorithmica 32, 1 (2002), 144–156.
[24]
Christos Levcopoulos, Giri Narasimhan, and Michiel H. M. Smid. 1998. Efficient algorithms for constructing fault-tolerant geometric spanners. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing(STOC’98), Jeffrey Scott Vitter (Ed.). ACM, New York, NY, 186–195.
[25]
R. J. Lipton and R. E. Tarjan. 1979. A separator theorem for planar graphs. SIAM J. Appl. Math. 36, 2 (1979), 177–189. arXiv:https://doi.org/10.1137/0136016
[26]
T. Lukovszki. 1999. New results of fault tolerant geometric spanners. In Proceedings of the 6th International Workshop on Algorithms and Data Structures.Springer-Verlag, Berlin, 193–204.
[27]
M. Mendel and A. Naor. 2007. Ramsey partitions and proximity data structures. J. Euro. Math. Soc. 009, 2 (2007), 253–275. http://eudml.org/doc/277787.
[28]
G. Narasimhan and M. Smid. 2007. Geometric Spanner Networks. Cambridge University Press, New York, NY.
[29]
D. Peleg. 2000. Distributed Computing: A Locality-Sensitive Approach. SIAM, 3600 University City Science Center, Philadelphia, PA. Retrieved from
[30]
D. Peleg and A. Schäffer. 1989. Graph spanners. J. Graph Theory 13 (1989), 99–116.
[31]
Doron Puder. 2015. Expansion of random graphs: New proofs, new results. Invent. Math. 201, 3 (2015), 845–908.
[32]
S. Solomon. 2014. From hierarchical partitions to hierarchical covers: Optimal fault-tolerant spanners for doubling metrics. In Proceedings of the 46th ACM Symposium on Theory of Computing (STOC’14). ACM, New York, NY, 363–372.
[33]
N. C. Wormald. 1999. Models of random regular graphs. In Surveys in Combinatorics, 1999 (Canterbury). London Math. Soc. Lecture Note Ser., Vol. 267. Cambridge University Press, Cambridge, UK, 239–298.
Index Terms
- Reliable Spanners for Metric Spaces
Recommendations
Fault-tolerant spanners for general graphs
STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computingThe paper concerns graph spanners that are resistant to vertex or edge failures. Given a weighted undirected n-vertex graph G=(V,E) and an integer k ≥ 1, the subgraph H=(V,E'), E'⊆ E, is a spanner of stretch k (or, a k-spanner) of G if δH(u,v) ≤ k· δG(u,...
Tree spanners on chordal graphs: complexity and algorithms
A tree t-spanner T in a graph G is a spanning tree of G such that the distance in T between every pair of vertices is at most t times their distance in G. The TREE t-SPANNER problem asks whether a graph admits a tree t-spanner, given t. We substantially ...
Spanners under the Hausdorff and Fréchet distances
AbstractWe initiate the study of spanners under the Hausdorff and Fréchet distances. Let S be a set of points in R d and ε a non-negative real number. A subgraph H of the Euclidean graph over S is an ε-Hausdorff-spanner (resp., an ε-Fréchet-spanner) of S,...
Highlights- We initiate the study of spanners under the Hausdorff and Fréchet distances.
- We show that any t-spanner of a planar point-set S is a f(t)-Hausdorff-spanner and a g(t)-Fréchet spanner.
- We prove that for any t > 1, there exist a set ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
January 2023
254 pages
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 ACM 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].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 09 March 2023
Online AM: 22 September 2022
Accepted: 06 September 2022
Revised: 31 August 2022
Received: 01 January 2022
Published in TALG Volume 19, Issue 1
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- NSF AF
- BSF
- Netherlands Organisation for Scientific Research (NWO)
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 133Total Downloads
- Downloads (Last 12 months)31
- Downloads (Last 6 weeks)2
Reflects downloads up to 05 Mar 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderFull Text
View this article in Full Text.
Full TextHTML Format
View this article in HTML Format.
HTML Format