Sparse source-wise and pair-wise distance preservers

ABSTRACT

We introduce and study the notions of pair-wise and source-wise preservers.Given an undirected N-vertex graph G = (V, E) and a subset P of pairs of vertices, let G' = (V, H), H ⊆ E, be called a pair-wise preserver of G with respect to P if for every pair {u, w} ∈ P, distG' (u, w) = distG (u, w). For a set S ⊆ V of sources, a pair-wise preserver of G with respect to the set of all pairs P = (S/2) of sources is called a source-wise preserver of G with respect to S.We prove that for every undirected possibly weighted N-vertex graph G and every subset P of P = O(N^1/2) pairs of vertices of G, there exists a linear-size pair-wise preserver of G with respect to P. Consequently, for every subset S ⊆ V of S = O(N^1/4) sources, there exists a linear-size source-wise preserver of G with respect to S. On the negative side we show that neither of the two exponents (1/2 and 1/4) can be improved even when the attention is restricted to unweighted graphs.Our lower bounds involve constructions of dense convexly independent sets of vectors with small Euclidean norms. We believe that the link between the areas of Discrete Geometry and spanners that we establish is of independent interest, and might be useful in the study of other problems in the area of low-distortion embeddings.

REFERENCES

• 1: Noga Alon , Richard M. Karp , David Peleg , Douglas West, A Graph-Theoretic Game and its Application to the $k$-Server Problem, SIAM Journal on Computing, v.24 n.1, p.78-100, Feb. 1995 [doi>10.1137/S0097539792224474]
• 2: 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]
• 3: B. Awerbuch and D. Peleg. Network synchronization with polylogarithmic overhead. In Proc. 31st Symp. on Foundations of Computer Science, pages 514--522, 1990.
• 4: Baruch Awerbuch , David Peleg, Routing with polynomial communication-space trade-off, SIAM Journal on Discrete Mathematics, v.5 n.2, p.151-162, May 1992 [doi>10.1137/0405013]
• 5: Baruch Awerbuch , Boaz Patt-Shamir , David Peleg , Michael Saks, Adapting to asynchronous dynamic networks (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.557-570, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129767]
• 6: A. Balog and I. Barany. On the convex hull of the integer points in a disc. Discrete and Computational Geometry, 6:39--44, 1991.
• 7: I. Barany and D. G. Larman. The convex hull of the integer points in a large ball. Mathematische Annalen, (312):167--181, 1998.
• 8: Surender Baswana , Telikepalli Kavitha , Kurt Mehlhorn , Seth Pettie, New constructions of (α, β)-spanners and purely additive spanners, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 9: S. Baswana and S. Sen. A simple linear time algorithm for computing a (2k -- 1)-spanner of o(n1+1/k) size in weighted graphs. In Proc. of the 30th International Colloq. on Automata, Languages and Computing, ICALP 2003, pages 284--296, 2003.
• 10: 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
• 11: J. Bourgain. On Lipschitz embedding of finite metric space in Hilbert space. Israel J. Math, 56:46--52, 1985.
• 12: E. Cohen. Fast algorithms for constructing t-spanners and paths of stretch t. In Proc. 34th IEEE Symp. on Foundations of Computer Science, pages 648--658, 1993.
• 13: D. Dor , S. Halperin , U. Zwick, All pairs almost shortest paths, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.452, October 14-16, 1996
• 14: 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]
• 15: 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]
• 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: G. H. Hardy and E. M. Wright. An Introduction to the Theory of Numbers. Oxford University Press, 1979.
• 18: P. Indyk and J. Matousek. Low Distortion Embeddings of Finite Metric Spaces: Chapter 8 in CRC Handbook of Discrete and Computational Geometry. 2004.
• 19: V. Jarnik. Uber Gitterpunkte und konvex Kurven. Math. Z., 2:500--518, 1925.
• 20: W. Johnson and J. Lindenstrauss. Extensions of Lipschitz embeddings into a Hilbert space. Contempt. Math., 26:189--206, 1984.
• 21: Y. Mansour , D. Peleg, An Approximation Algorithm for Minimum-Cost Network Design, Weizmann Science Press of Israel, Jerusalem, Israel, 1994
• 22: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 23: D. Peleg. Proximity-preserving labeling schemes. Journal of Graph Theory, (33):167--176, 2000.
• 24: D. Peleg and A. Schäffer. Graph spanners. Journal of Graph Theory, 13:99--116, 1989.
• 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: Liam Roditty , Mikkel Thorup , Uri Zwick, Roundtrip spanners and roundtrip routing in directed graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.844-851, January 06-08, 2002, San Francisco, California
• 27: 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]