Fault-tolerant spanners for general graphs

ABSTRACT

The 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,v) for every u,v ∈ V, where δ_G'(u,v) denotes the distance between u and v in G'. Graph spanners were extensively studied since their introduction over two decades ago. It is known how to efficiently construct a (2k-1)-spanner of size O(n^1+1/k), and this size-stretch tradeoff is conjectured to be tight. The notion of fault tolerant spanners was introduced a decade ago in the geometric setting [Levcopoulos et al., STOC'98]. A subgraph H is an f-vertex fault tolerant k-spanner of the graph G if for any set F⊆ V of size at most f and any pair of vertices u,v ∈ V \ F, the distances in H satisfy δ_{H \ F}(u,v) ≤ k· δ_{G \ F}(u,v). Levcopoulos et al. presented an efficient algorithm that given a set S of n points in R^d, constructs an f-vertex fault tolerant geometric (1+ε)-spanner for S, that is, a sparse graph H such that for every set F⊆ S of size f and any pair of points u,v ∈ S \ F, δ_{H \ F}(u,v) ≤ (1+ε) |uv|, where |uv| is the Euclidean distance between u and v. A fault tolerant geometric spanner with optimal maximum degree and total weight was presented in [Czumaj &#; Zhao, SoCG'03]. This paper also raised as an open problem the question whether it is possible to obtain a fault tolerant spanner for an arbitrary undirected weighted graph. The current paper answers this question in the affirmative, presenting an f-vertex fault tolerant (2k-1)-spanner of size O(f² k^f+1 · n^1+1/klog^1-1/kn). Interestingly, the stretch of the spanner remains unchanged while the size of the spanner only increases by a factor that depends on the stretch k, on the number of potential faults f, and on logarithmic terms in n. In addition, we consider the simpler setting of f-edge fault tolerant spanners (defined analogously). We present an f-edge fault tolerant 2k-1 spanner with edge set of size O(f· n^1+1/k) (only f times larger than standard spanners). For both edge and vertex faults, our results are shown to hold when the given graph G is weighted.

REFERENCES

• 1: Ingo Althöfer , Gautam Das , David Dobkin , Deborah Joseph , José Soares, On sparse spanners of weighted graphs, Discrete & Computational Geometry, v.9 n.1, p.81-100, 1993 [doi>10.1007/BF02189308]
• 2: B. Awerbuch , B. Berger , L. Cowen , D. Peleg, Near-linear cost sequential and distributed constructions of sparse neighborhood covers, Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science, p.638-647, November 03-05, 1993 [doi>10.1109/SFCS.1993.366823]
• 3: Surender Baswana , Telikepalli Kavitha, Faster Algorithms for Approximate Distance Oracles and All-Pairs Small Stretch Paths, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.591-602, October 21-24, 2006 [doi>10.1109/FOCS.2006.29]
• 4: Surender Baswana , Soumojit Sarkar, Fully dynamic algorithm for graph spanners with poly-logarithmic update time, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1125-1134, January 20-22, 2008, San Francisco, California
• 5: Surender Baswana , Sandeep Sen, Approximate distance oracles for unweighted graphs in expected O(n²) time, ACM Transactions on Algorithms (TALG), v.2 n.4, p.557-577, October 2006 [doi>10.1145/1198513.1198518]
• 6: Aaron Bernstein , David Karger, Improved distance sensitivity oracles via random sampling, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.34-43, January 20-22, 2008, San Francisco, California
• 7: Béla Bollobás , Don Coppersmith , Michael Elkin, Sparse distance preservers and additive spanners, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 8: Artur Czumaj , Hairong Zhao, Fault-Tolerant Geometric Spanners, Discrete & Computational Geometry, v.32 n.2, p.207-230, July 2004 [doi>10.1007/s00454-004-1121-7]
• 9: Camil Demetrescu , Mikkel Thorup , Rezaul Alam Chowdhury , Vijaya Ramachandran, Oracles for Distances Avoiding a Failed Node or Link, SIAM Journal on Computing, v.37 n.5, p.1299-1318, January 2008 [doi>10.1137/S0097539705429847]
• 10: Ran Duan , Seth Pettie, Dual-failure distance and connectivity oracles, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.506-515, January 04-06, 2009, New York, New York
• 11: Devdatt Dubhashi , Alessandro Mei , Alessandro Panconesi , Jaikumar Radhakrishnan , Aravind Srinivasan, Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons, Journal of Computer and System Sciences, v.71 n.4, p.467-479, November 2005 [doi>10.1016/j.jcss.2005.04.002]
• 12: Michael Elkin, Computing almost shortest paths, ACM Transactions on Algorithms (TALG), v.1 n.2, p.283-323, October 2005 [doi>10.1145/1103963.1103968]
• 13: Michael Elkin, A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281128]
• 14: M. Elkin. Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. In Proc. 34th ICALP, pages 716--727, 2007.
• 15: Michael Elkin , Jian Zhang, Efficient algorithms for constructing (1+,ε, β)-spanners in the distributed and streaming models, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011791]
• 16: Arthur M. Farley , Andrzej Proskurowski , Daniel Zappala , Kurt Windisch, Spanners and message distribution in networks, Discrete Applied Mathematics, v.137 n.2, p.159-171, 1 March 2004 [doi>10.1016/S0166-218X(03)00259-2]
• 17: Jie Gao , Leonidas J. Guibas , An Nguyen, Deformable spanners and applications, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997848]
• 18: Lee-Ad Gottlieb , Liam Roditty, Improved algorithms for fully dynamic geometric spanners and geometric routing, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.591-600, January 20-22, 2008, San Francisco, California
• 19: Lee-Ad Gottlieb , Liam Roditty, An Optimal Dynamic Spanner for Doubling Metric Spaces, Proceedings of the 16th annual European symposium on Algorithms, September 15-17, 2008, Karlsruhe, Germany [doi>10.1007/978-3-540-87744-8_40]
• 20: Christos Levcopoulos , Giri Narasimhan , Michiel Smid, Efficient algorithms for constructing fault-tolerant geometric spanners, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.186-195, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276734]
• 21: Tamás Lukovszki, New Results of Fault Tolerant Geometric Spanners, Proceedings of the 6th International Workshop on Algorithms and Data Structures, p.193-204, August 11-14, 1999
• 22: Mihai Patrascu , Mikkel Thorup, Planning for Fast Connectivity Updates, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.263-271, October 21-23, 2007 [doi>10.1109/FOCS.2007.54]
• 23: D. Peleg and A. A. Scháffer. Graph spanners. J. Graph Theory, pages 99--116, 1989.
• 24: David Peleg , Jeffrey D. Ullman, An optimal synchronizer for the hypercube, SIAM Journal on Computing, v.18 n.4, p.740-747, Aug. 1989 [doi>10.1137/0218050]
• 25: David Peleg , Eli Upfal, A trade-off between space and efficiency for routing tables, Journal of the ACM (JACM), v.36 n.3, p.510-530, July 1989 [doi>10.1145/65950.65953]
• 26: S. Pettie. Low distortion spanners. In Proc. 34th ICALP, pages 78--89, 2007.
• 27: Liam Roditty, Fully dynamic geometric spanners, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea [doi>10.1145/1247069.1247134]
• 28: L. Roditty, M. Thorup, and U. Zwick. Deterministic constructions of approximate distance oracles and spanners. In Proc. 32th ICALP, pages 261--272, 2005.
• 29: L. Roditty and U. Zwick. On dynamic shortest paths problems. In Proc. 12th ESA, 2004.
• 30: J. S. Salowe. Constructing multidimensional spanner graphs. Int. J. Comput. Geom. Appl., 1(2):99--107, 1991.
• 31: Mikkel Thorup , Uri Zwick, Compact routing schemes, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.1-10, July 2001, Crete Island, Greece [doi>10.1145/378580.378581]
• 32: Mikkel Thorup , Uri Zwick, Approximate distance oracles, Journal of the ACM (JACM), v.52 n.1, p.1-24, January 2005 [doi>10.1145/1044731.1044732]
• 33: Mikkel Thorup , Uri Zwick, Spanners and emulators with sublinear distance errors, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.802-809, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109645]
• 34: Pravin M. Vaidya, A sparse graph almost as good as the complete graph on points in K dimensions, Discrete & Computational Geometry, v.6 n.4, p.369-381, 1991 [doi>10.1007/BF02574695]
• 35: David P. Woodruff, Lower Bounds for Additive Spanners, Emulators, and More, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.389-398, October 21-24, 2006 [doi>10.1109/FOCS.2006.45]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory

Keywords:
fault-tolerance, graphs, spanners