The 4/3 additive spanner exponent is tight

ABSTRACT

A spanner is a sparse subgraph that approximately preserves the pairwise distances of the original graph. It is well known that there is a smooth tradeoff between the sparsity of a spanner and the quality of its approximation, so long as distance error is measured multiplicatively. A central open question in the field is to prove or disprove whether such a tradeoff exists also in the regime of additive error. That is, is it true that for all ε>0, there is a constant k_ε such that every graph has a spanner on O(n^1+ε) edges that preserves its pairwise distances up to +k_ε? Previous lower bounds are consistent with a positive resolution to this question, while previous upper bounds exhibit the beginning of a tradeoff curve: all graphs have +2 spanners on O(n^3/2) edges, +4 spanners on Õ(n^7/5) edges, and +6 spanners on O(n^4/3) edges. However, progress has mysteriously halted at the n^4/3 bound, and despite significant effort from the community, the question has remained open for all 0 < ε < 1/3.

Our main result is a surprising negative resolution of the open question, even in a highly generalized setting. We show a new information theoretic incompressibility bound: there is no function that compresses graphs into O(n^{4/3 − ε}) bits so that distance information can be recovered within +n^o(1) error. As a special case of our theorem, we get a tight lower bound on the sparsity of additive spanners: the +6 spanner on O(n^4/3) edges cannot be improved in the exponent, even if any subpolynomial amount of additive error is allowed. Our theorem implies new lower bounds for related objects as well; for example, the twenty-year-old +4 emulator on O(n^4/3) edges also cannot be improved in the exponent unless the error allowance is polynomial.

Central to our construction is a new type of graph product, which we call the Obstacle Product. Intuitively, it takes two graphs G,H and produces a new graph G H whose shortest paths structure looks locally like H but globally like G.

References

1. Amir Abboud and Greg Bodwin. Error Amplification for Pairwise Spanner Lower Bounds. In Proc. of 27th SODA, to appear, 2016.
2. Donald Aingworth, Chandra Chekuri, Piotr Indyk, and Rajeev Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput., 28:1167–1181, 1999.
3. Donald Aingworth, Chandra Chekuri, and Rajeev Motwani. Fast Estimation of Diameter and Shortest Paths (without Matrix Multiplication). In Proc. of 7th SODA., pages 547–553, 1996.
4. Noga Alon. Testing subgraphs in large graphs. In Proc. of 42nd FOCS, pages 434–441, 2001.
5. I Althöfer, G Das, D Dobkin, D Joseph, and J Soares. On sparse spanners of weighted graphs. Discrete &amp; Computational Geometry, 9:81–100, 1993.
6. Baruch Awerbuch. Complexity of network synchronization. Journal of the ACM, pages 32,804–823, 1985.
7. Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie. New constructions of (α, β)-spanners and purely additive spanners. In Proc. of 16th SODA, pages 672–681, 2005.
8. Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie. Additive spanners and (α, β)-spanners. ACM Transactions on Algorithms, 7(1):5, 2010.
9. Felix A Behrend. On sets of integers which contain no three terms in arithmetical progression. Proceedings of the National Academy of Sciences of the United States of America, 32(12):331, 1946.
10. Greg Bodwin and Virginia Vassilevska Williams. Very Sparse Additive Spanners and Emulators. In Proc. of 6th ITCS, pages 377–382, 2015.
11. Greg Bodwin and Virginia Vassilevska Williams. Better Distance Preservers and Additive Spanners. In Proc. of 27th SODA, to appear, 2016.
12. Béla Bollobás, Don Coppersmith, and Michael Elkin. Sparse distance preservers and additive spanners. In Proc. of 14th SODA, pages 414–423, 2003.
13. Jean Bourgain. On lipschitz embedding of finite metric spaces in hilbert space. Israel Journal of Mathematics, 52(1-2):46–52, 1985.
14. Shiri Chechik. New Additive Spanners. In Proc. of 24th SODA, pages 498–512, 2013.
15. Shiri Chechik. Additive Spanners. In Encyclopedia of Algorithms. 2014.
16. Don Coppersmith and Michael Elkin. Sparse Sourcewise and Pairwise Distance Preservers. SIAM Journal on Discrete Mathematics, pages 463–501, 2006.
17. Marek Cygan, Fabrizio Grandoni, and Telikepalli Kavitha. On Pairwise Spanners. In Proc. of 30th STACS, pages 209–220, 2013.
18. Dorit Dor, Shay Halperin, and Uri Zwick. All Pairs Almost Shortest Paths. In Proc. of 37th FOCS, pages 452–461, 1996.
19. Michael Elkin. Computing almost shortest paths. ACM Trans. Algorithms, pages 1(2):283–323, 2005.
20. Michael Elkin and David Peleg. (1 +, β)-spanner constructions for general graphs. SIAM J. Comput., 33(3):608ˆ a ˘ A¸ S631, 2004.
21. Paul Erdös. Extremal problems in graph theory. Theory of graphs and its applications, pages 29–36, 1964.
22. Telikepalli Kavitha. New Pairwise Spanners. In Proc. of 32nd STACS, pages 513–526, 2015.
23. Telikepalli Kavitha and Nithin Varma. Small Stretch Pairwise Spanners. In Proc. of 40th ICALP, pages 601–612, 2013.
24. Mathias Bæk Tejs Knudsen. Additive spanners: A simple construction. In Proc. of 14th SWAT, pages 277–281, 2014.
25. Arthur L. Liestman and Thomas C. Shermer. Additive spanners for hypercubes. Parallel Processing Letters, 1(01):35–42, 1991.
26. Arthur L. Liestman and Thomas C. Shermer. Additive graph spanners. Networks, 23(4):343–363, 1993.
27. Jiˇ r´ı Matouˇ sek. On the distortion required for embedding finite metric spaces into normed spaces. Israel Journal of Mathematics, 93(1):333–344, 1996.
28. Merav Parter. Bypassing Erdös’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners. In Proc. of 41st ICALP, pages 608–619, 2014.
29. David Peleg and Alejandro Schaffer. Graph spanners. Journal of Graph Theory, pages 13:99–116, 1989.
30. David Peleg and Jeffrey D. Ullman. An optimal synchronizer for the hypercube. SIAM Journal of Computing, pages 18,740–747, 1989.
31. Seth Pettie. Low distortion spanners. ACM Transactions on Algorithms, 6(1), 2009.
32. Liam Roditty, Mikkel Thorup, and Uri Zwick. Deterministic Constructions of Approximate Distance Oracles and Spanners. In Proc. of 32nd ICALP, pages 261–272, 2005.
33. Mikkel Thorup and Uri Zwick. Approximate distance oracles. Journal of the ACM, 52(1):1–24, 2005.
34. Mikkel Thorup and Uri Zwick. Spanners and emulators with sublinear distance errors. In Proc. of 17th SODA, pages 802–809, 2006.
35. David P. Woodruff. Lower bounds for additive spanners, emulators, and more. In Proc. of 47th FOCS, pages 389–398, 2006.
36. David P. Woodruff. Additive Spanners in Nearly Quadratic Time. In Proc. of 37th ICALP, pages 463–474, 2010.
37. Graphs with many longdisjoint shortest paths

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

• Theory of computation

  • Design and analysis of algorithms