Sparse distance preservers and additive spanners

ABSTRACT

For an unweighted graph G = (V, E), G′ = (V, E′) is a subgraph if E′ ⊆ E, and G″ = (V″, E″, ω) is a Steiner graph if V ⊆ V″, and for any pair of vertices u, w ∈ V, the distance bet-ween them in G″(denoted dG″, (u, w)) is at least the distance between them in G (denoted da(u, w)).In this paperwe introduce the notion of distance preserver. A subgraph (resp., Steiner graph) G′ of a graph G is a subgraph (resp., Steiner) D-preserver of G if for every pair of vertices u, w ∈ V with dG(u, w) ≥ D, dG′, (u, w) = dG(u, w). We show that anygraph (resp., digraph) has a subgraph D-preserver with at most O(n²/D) edges (resp., arcs), and there are graphs and digraphs for which any undirected Steiner D-preserver contains Ω(n²/D) edges. However, we show that if one allows a directed Steiner (or, shortly, diS-teiner) D-preserver, then these bounds can be improved. Specifically, we show that for any graph or digraph there exists a diSteiner D-preserver with O(n².log D/D.log n arcs, and that this result is tight up to a constant factor.We also study D-preserving distance labeling schemes, that are labeling schemes that guarantee precise calculation ofdistances between pairs of vertices that are at distance at least D one from another. We show that there exists a D-preserving labeling scheme with labels of size O(n/Dlog² n), and that labels of size Ω(n/D log D) are required for any D-preserving labeling scheme.Finally, we study additive spanners. A subgraph G′ of an undirected graph G = (V, E) is its additive β-spanner if for any pair of vertices u, w ∈ V, dG′, (u, w) ≤ dG(u, w)+β. It is known that for any n-vertex graph there exists an additive 2-spanner with O(n^3/2) edges, and an additive Steiner 4-spanner with O(n^4/3) edges. However, no construction of additive spanners with o(n^3/2) edges or Steiner additive spanners with o(n^4/3) edges are known so far. We devise a construction of additive O(2^1/δn^(1-δ)[1/δ]--2/[1/δ]--1)-spanner with O(n^1+δ) edges for any graph and any δ < 0.

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 and D. Peleg, Sparse partitions, Proc. 31st IEEE Symp. on Foundations of Computer Science, 503--513, October 1990.
• 3: B. Awerbuch and D. Peleg. Network synchronization with polylogarithmic overhead, In Proc. 31st Symp. on Foundations of Computer Science, pp. 514--522, October, 1990.
• 4: Baruch Awerbuch , Bonnie Berger , Lenore Cowen , David Peleg, Near-Linear Time Construction of Sparse Neighborhood Covers, SIAM Journal on Computing, v.28 n.1, p.263-277, Feb. 1999 [doi>10.1137/S0097539794271898]
• 5: Bollobás, B., Modern Graph Theory, Graduate Texts in Mathematics, vol. 184, Springer-Verlag, New York, 1998, xiv+394 pp. (OR, Second Edition, 2002)
• 6: Bollobás, B., Random Graphs, Second Edition, Cambridge Studies in Advanced Mathematics 73, Cambridge University Press, Cambridge, 2001, xviii+498 pp.
• 7: 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]
• 8: 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]
• 9: E. Cohen, Fast Algorithms for constructing t-spanners and paths of stretch t, in Proc. 30th IEEE Syrup. on Foundations of Computer Science, IEEE, Piscataway, NJ, 1993, 648--658.
• 10: Edith Cohen, Polylog-time and near-linear work approximation scheme for undirected shortest paths, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.16-26, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195089]
• 11: 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.
• 12: 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]
• 13: Michael Elkin, Computing almost shortest paths, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.53-62, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.383983]
• 14: Michael Elkin , David Peleg, (1 + &egr;&Bgr;)-spanner constructions for general graphs, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.173-182, July 2001, Hersonissos, Greece [doi>10.1145/380752.380797]
• 15: Tomás Feder , Rajeev Motwani, Clique partitions, graph compression and speeding-up algorithms, Journal of Computer and System Sciences, v.51 n.2, p.261-272, Oct. 1995 [doi>10.1006/jcss.1995.1065]
• 16: Cyril Gavoille , David Peleg , Stéphane Pérennes , Ran Raz, Distance labeling in graphs, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.210-219, January 07-09, 2001, Washington, D.C., United States
• 17: R. L. Graham, B. L. Rothschield, J. H. Spencer, Ramsey Theory, Second Edition, Wiley-Interscience Series in Discrete Mathematics and Optimization, A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1990, xii+196 pp.
• 18: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 19: D. Peleg, Proximity-preserving labeling schemes, J. Graph Theory, 33:167--176, 2000.
• 20: D. Peleg and A. Schäffer. Graph Spanners, Journal of Graph Theory13 (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: M. Thorup, Oct. 2001, private communication.
• 23: M. Thorup, Compact Oracles for Reachability and Approximate Distances in Planar Digraphs, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.242, October 14-17, 2001
• 24: Mikkel Thorup , Uri Zwick, Approximate distance oracles, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.183-192, July 2001, Hersonissos, Greece [doi>10.1145/380752.380798]
• 25: Jeffrey D. Ullman , Mihalis Yannakakis, High probability parallel transitive-closure algorithms, SIAM Journal on Computing, v.20 n.1, p.100-125, Feb. 1991 [doi>10.1137/0220006]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.m MISCELLANEOUS

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.m Miscellaneous

General Terms:
Algorithms, Theory