Additive spanners and (α, β)-spanners

Abstract

An (α, β)-spanner of an unweighted graph G is a subgraph H that distorts distances in G up to a multiplicative factor of α and an additive term β. It is well known that any graph contains a (multiplicative) (2k−1, 0)-spanner of size O(n^1+1/k) and an (additive) (1,2)-spanner of size O(n^3/2). However no other additive spanners are known to exist.

In this article we develop a couple of new techniques for constructing (α, β)-spanners. Our first result is an additive (1,6)-spanner of size O(n^4/3). The construction algorithm can be understood as an economical agent that assigns costs and values to paths in the graph, purchasing affordable paths and ignoring expensive ones, which are intuitively well approximated by paths already purchased. We show that this path buying algorithm can be parameterized in different ways to yield other sparseness-distortion tradeoffs. Our second result addresses the problem of which (α, β)-spanners can be computed efficiently, ideally in linear time. We show that, for any k, a (k,k−1)-spanner with size O(kn^1+1/k) can be found in linear time, and, further, that in a distributed network the algorithm terminates in a constant number of rounds. Previous spanner constructions with similar performance had roughly twice the multiplicative distortion.

References

1. Abraham, I., Bartal, Y., Chan, H. T.-H., Dhamdhere, K., Gupta, A., Kleinberg, J. M., Neiman, O., and Slivkins, A. 2005. Metric embeddings with relaxed guarantees. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 83--100.
2. Abraham, I., Bartal, Y., and Neiman, O. 2006a. Advances in metric embedding theory. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC). 271--286.
3. Abraham, I., Bartal, Y., and Neiman, O. 2007. Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA). 502--511.
4. Abraham, I., Gavoille, C., and Malkhi, D. 2006b. On space-stretch trade-offs: upper bounds. In Proceedings of the 18th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA). 217--224.
5. Aggarwal, A., and Vitter, J. S. 1988. The input/output complexity of sorting and related problems. Comm. ACM 31, 9, 1116--1127.
6. Aingworth, D., Chekuri, C., Indyk, P., and Motwani, R. 1999. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput. 28, 4, 1167--1181.
7. Alon, N., Hoory, S., and Linial, N. 2002. The Moore bound for irregular graphs. Graphs Combin. 18, 1, 53--57.
8. Alon, N., Karp, R. M., Peleg, D., and West, D. B. 1995. A graph-theoretic game and its application to the k-server problem. SIAM J. Comput. 24, 1, 78--100.
9. Althöfer, I., Das, G., Dobkin, D., Joseph, D., and Soares, J. 1993. On sparse spanners of weighted graphs. Discrete Comput. Geom. 9, 81--100.
10. Bǎdoiu, M., Indyk, P., and Sidiropoulos, A. 2007. Approximation algorithms for embedding general metrics into trees. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA).
11. Bartal, Y. 1996. Probabilistic approximations of metric spaces and its algorithmic applications. In Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 184--193.
12. Baswana, S., Gaur, A., Sen, S., and Upadhyay, J. 2008. Distance oracles for unweighted graphs: Breaking the quadratic barrier with constant additive error. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 5125. Springer, Berlin, Germany, 609--621.
13. Baswana, S., and Kavitha, T. 2006. Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In Proceedings of the 47th IEEE Symposium on Foundations of Computer Science (FOCS). 591--602.
14. Baswana, S., Kavitha, T., Mehlhorn, K., and Pettie, S. 2005. New constructions of (α, β)-spanners and purely additive spanners. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA). 672--681.
15. Baswana, S., and Sen, S. 2003. A simple linear time algorithm for computing a (2k−1)-spanner of O(n^1+1/k) size in weighted graphs. In Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP).
16. Baswana, S., and Sen, S. 2006. Approximate distance oracles for unweighted graphs in expected O(n² log n) time. ACM Trans. Algor. 2, 4, 557--577.
17. Baswana, S., and Sen, S. 2007. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. J. Rand. Struct. Algor. 30, 4, 532--563.
18. Bollobás, B., Coppersmith, D., and Elkin, M. 2003. Sparse distance preservers and additive spanners. In Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA). 414-- 423.
19. Chan, H. T.-H., Dinitz, M., and Gupta, A. 2006. Spanners with slack. In Proceedings of the 14th Annual European Symposium on Algorithms (ESA). 196--207.
20. Chan, H. T.-H., and Gupta, A. 2006. Small hop-diameter sparse spanners for doubling metrics. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 70--78.
21. Chan, H. T.-H., Gupta, A., Maggs, B. M., and Zhou, S. 2005. On hierarchical routing in doubling metrics. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 762--771.
22. Cohen, E. 1998. Fast algorithms for constructing t-spanners and paths with stretch t. SIAM J. Comput. 28, 210--236.
23. Cohen, E. 2000. Polylog-time and near-linear work approximation scheme for undirected shortest-paths. J. ACM 47, 132--166.
24. Coppersmith, D., and Elkin, M. 2005. Sparse source-wise and pair-wise distance preservers. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA). 660--669.
25. Cowen, L. J. 2001. Compact routing with minimum stretch. J. Algor. 28, 170--183.
26. Cowen, L. J., and Wagner, C. G. 2004. Compact roundtrip routing in directed networks. J. Algor. 50, 1, 79--95.
27. Dor, D., Halperin, S., and Zwick, U. 2000. All-pairs almost shortest paths. SIAM J. Comput. 29, 5, 1740--1759.
28. Elkin, M. 2004. Private communication.
29. Elkin, M. 2005. Computing almost shortest paths. ACM Trans. Algor. 1, 2, 283--323.
30. Elkin, M., Emek, Y., Spielman, D. A., and Teng, S.-H. 2005. Lower-stretch spanning trees. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC). 494--503.
31. Elkin, M., and Peleg, D. 2001. (1+ε, β)-spanner constructions for general graphs. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC). 173--182.
32. Elkin, M., and Peleg, D. 2004. (1+ε, β)-spanner constructions for general graphs. SIAM J. Comput. 33, 3, 608--631.
33. Elkin, M., and Peleg, D. 2005. Approximating k-spanner problems for k≥ 2. Theoret. Comput. Sci. 337, 1--3, 249--277.
34. Elkin, M., and Zhang, J. 2006. Efficient algorithms for constructing (1+ε, β)-spanners in the distributed and streaming models. Distrib. Comput. 18, 5, 375--385.
35. Emek, Y., and Peleg, D. 2004. Approximating minimum max-stretch spanning trees on unweighted graphs. In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA). 261--270.
36. Erdős, P. 1963. Extremal problems in graph theory. In Theory of Graphs and its Applications. Publishing House of the Czechoslovak Academy of Sciences, Prague, Chechoslovakia, 29--36.
37. Fakcharoenphol, J., Rao, S., and Talwar, K. 2004. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci. 69, 3, 485--497.
38. Frigo, M., Leiserson, C. E., Prokop, H., and Ramachandran, S. 1999. Cache-oblivious algorithms. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 285--298.
39. Gudmundsson, J., Levcopoulos, C., and Narasimhan, G. 2002. Fast greedy algorithms for constructing sparse geometric spanners. SIAM J. Comput. 31, 5, 1479--1500.
40. Halperin, S., and Zwick, U. 1996. Unpublished.
41. Har-Peled, S., and Mendel, M. 2006. Fast construction of nets in low-dimensional metrics and their applications. SIAM J. Comput. 35, 5, 1148--1184.
42. Indyk, P. 2001. Algorithmic aspects of low-distortion geometric embeddings. 42nd Annual IEEE Symposium on Foundations of Computer Science. Tutorial. http://theory.lcs.mit.edu/~indyk/tut.html.
43. Indyk, P., and Matousek, J. 2004. Low-distortion embedding of finite metric spaces. In Handbook of Discrete and Computational Geometry, 2nd ed. CRC Press, Boca Raton, FL.
44. Karp, R. M., and Ramachandran, V. 1990. Parallel algorithms for shared-memory machines. In Handbook of Computer Science. MIT Press, Cambridge, MA, 869--942.
45. Mendel, M., and Naor, A. 2007. Ramsey partitions and proximity data structures. J. European Math. Soc 9, 2, 253--275.
46. Narasimhan, G., and Smid, M. 2007. Geometric Spanner Networks. Cambridge University Press, Cambridge, U.K.
47. Peleg, D. 2000. Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia, PA.
48. Peleg, D., and Schaffer, A. A. 1989. Graph spanners. J. Graph Theor. 13, 99--116.
49. Peleg, D., and Ullman, J. D. 1989. An optimal synchronizer for the hypercube. SIAM J. Comput. 18, 740--747.
50. Peleg, D., and Upfal, E. 1989. A trade-off between space amd efficiency for routing tables. J. ACM 36, 3, 510--530.
51. Pettie, S. 2007. Low distortion spanners. In Proceedings of the 34th International Colloquium on Automata, Languages, and Programming (ICALP). 78--89.
52. Roditty, L., Thorup, M., and Zwick, U. 2002. Roundtrip spanners and roundtrip routing in directed graphs. In Proceedings of the 13th ACM-SIAM Symposium On Discrete Algorithms (SODA). 844-- 851.
53. Roditty, L., Thorup, M., and Zwick, U. 2005. Deterministic constructions of approximate distance oracles and spanners. In Proceedings of the 32nd International Colloquium on Automata, Language, and Programming (ICALP). 261--272.
54. Roditty, L., and Zwick, U. 2004. On dynamic shortest paths problems. In Proceedings of the 12th Annual European Symposium on Algorithms (ESA). 580--591.
55. Spielman, D. A., and Teng, S.-H. 2004. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC). 81--90.
56. Thorup, M., and Zwick, U. 2001. Compact routing schemes. In Proceedings of the 13th ACM Symposium on Parallel Algorithms and Architectures (SPAA). 1--10.
57. Thorup, M., and Zwick, U. 2005. Approximate distance oracles. J. ACM 52, 1, 1--24.
58. Thorup, M., and Zwick, U. 2006. Spanners and emulators with sublinear distance errors. In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA). 802--809.
59. Wenger, R. 1991. Extremal graphs with no C⁴s, C⁶s, or C¹⁰s. J. Comb. Theor. Ser. B 52, 1, 113--116.
60. Woodruff, D. 2006. Lower bounds for additive spanners, emulators, and more. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 389--398.
61. Xiao, J., Liu, L., Xia, L., and Jiang, T. 2007. Fast elimination of redundant linear equations and reconstruction of recombination-free Mendelian inheritance on a pedigree. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 655--664.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms