(1 + &egr;&Bgr;)-spanner constructions for general graphs

ABSTRACT

An (&agr;,&Bgr;)-spanner of a graph G is a subgraph H such that d_H(u,w)\le &agr\cdot d_G(u,w)+&Bgr for every pair of vertices u,w, where d_{G'}(u,w) denotes the distance between two vertices u and v in G'. It is known that every graph G has a polynomially constructible (2&kgr;-1,0)-spanner (a.k.a. multiplicative (2&kgr;-1)-spanner) of size O(n^{1+1/&kgr}) for every integer &kgr\ge 1, and a polynomially constructible (1,2)-spanner (a.k.a. additive 2-spanner) of size \tO(n^{3/2}). This paper explores hybrid spanner constructions (involving both multiplicative and additive factors) for general graphs and shows that the multiplicative factor can be made arbitrarily close to 1 while keeping the spanner size arbitrarily close to O(n), at the cost of allowing the additive term to be a sufficiently large constant. More formally, we show that for any constant &egr, &dgr > 0 there exists a constant &Bgr = &Bgr(&egr, &dgr) such that for every n-vertex graph G there is an efficiently constructible (1+ &egr, &Bgr)-spanner of size O(n^{1 + &dgr}). It follows that for any constant &egr, &dgr > 0 there exists a constant &Bgr(&egr, &dgr) such that for any n-vertex graph G = (V,E) there exists an efficiently constructible subgraph (V,H) with O(n^{1 +&dgr}) edges such that d_H(u,w) \le (1 + &egr) d_G(u,w) for every pair of vertices.

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: Baruch Awerbuch and David Peleg, Sparse partitions, Proc. 31st IEEE Symp. on Foundations of Computer Science, 503-513, October 1990.
• 3: Robert D. Carr , Srinivas Doddi , Goran Konjevod , Madhav Marathe, On the red-blue set cover problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.345-353, January 09-11, 2000, San Francisco, California, United States
• 4: Barun Chandra , Gautam Das , Giri Narasimhan , José Soares, New sparseness results on graph spanners, Proceedings of the eighth annual symposium on Computational geometry, p.192-201, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142717]
• 5: P Chew, There is a planar graph almost as good as the complete graph, Proceedings of the second annual symposium on Computational geometry, p.169-177, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10534]
• 6: D.P. Dobkin, S.J. Friedman and K.J. Supowit, Delaunay graphs are almost as good as complete graphs, Proc. 31st IEEE Symp. on Foundations of Computer Science, 1987, 20-26.
• 7: Dorit Dor , Shay Halperin , Uri Zwick, All-Pairs Almost Shortest Paths, SIAM Journal on Computing, v.29 n.5, p.1740-1759, March 2000 [doi>10.1137/S0097539797327908]
• 8: Yevgeniy Dodis , Sanjeev Khanna, Design networks with bounded pairwise distance, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.750-759, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301447]
• 9: Michael Elkin , David Peleg, The Hardness of Approximating Spanner Problems, Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, p.370-381, February 01, 2000
• 10: Michael Elkin , David Peleg, Strong Inapproximability of the Basic k-Spanner Problem, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.636-647, July 09-15, 2000
• 11: M. Elkin , D. Peleg, The Client-Server 2-Spanner Problem and Applications to Network Design, Weizmann Science Press of Israel, Jerusalem, Israel, 1999
• 12: M. Elkin , D. Peleg, Approximating k-Spanner Problems for k < 2, Weizmann Science Press of Israel, Jerusalem, Israel, 2000
• 13: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 14: Guy Kortsarz, On the Hardness of Approximation Spanners, Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization, p.135-146, July 18-19, 1998
• 15: Guy Kortsarz , David Peleg, Generating sparse 2-spanners, Journal of Algorithms, v.17 n.2, p.222-236, Sept. 1994 [doi>10.1006/jagm.1994.1032]
• 16: C. Li, S. McCormick and D. Simchi-Levi, On the Minimum-Cardinality-Bounded-Diameter and Bounded-cardinality-minimum-diameter Edge Addition Problems, Operation Research Letters 11, (1992), 303-308.
• 17: A.L. Liestman and T.C. Shermer, Additive Graph Spanners, Tech. Report No 91-5, Simon Fraser University, 1991.
• 18: A.L. Liestman and T.Shermer, Grid Spanners, Networks 23, (1993), 123-133.
• 19: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 20: D. Peleg and A. Schaer, Graph Spanners, J. Graph Theory 13, (1989), 99-116.
• 21: 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]
• 22: R. Wenger, Extremal graphs with no C4,s, or C10,s, Journal of Combinatorial Theory Series B, v.52 n.1, p.113-116, May 1991 [doi>10.1016/0095-8956(91)90097-4]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional 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, Measurement, Performance, Theory, Verification