Document Open Access Logo

The Norms of Graph Spanners

Authors Eden Chlamtáč, Michael Dinitz, Thomas Robinson

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.40.pdf
  • Filesize: 498 kB
  • 15 pages

Document Identifiers

Author Details

Eden Chlamtáč
  • Ben Gurion University of the Negev, Beersheva, Israel
Michael Dinitz
  • Johns Hopkins University, Baltimore, MD, USA
Thomas Robinson
  • Ben Gurion University of the Negev, Beersheva, Israel

Funding

  • Chlamtáč, Eden: Supported in part by ISF grant 1002/14.
  • Dinitz, Michael: Supported in part by NSF awards CCF-1464239 and CCF-1535887.
  • Robinson, Thomas: Supported in part by ISF grant 1002/14.

Cite AsGet BibTex

Eden Chlamtáč, Michael Dinitz, and Thomas Robinson. The Norms of Graph Spanners. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 40:1-40:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.40

Abstract

A t-spanner of a graph G is a subgraph H in which all distances are preserved up to a multiplicative t factor. A classical result of Althöfer et al. is that for every integer k and every graph G, there is a (2k-1)-spanner of G with at most O(n^{1+1/k}) edges. But for some settings the more interesting notion is not the number of edges, but the degrees of the nodes. This spurred interest in and study of spanners with small maximum degree. However, this is not necessarily a robust enough objective: we would like spanners that not only have small maximum degree, but also have "few" nodes of "large" degree. To interpolate between these two extremes, in this paper we initiate the study of graph spanners with respect to the l_p-norm of their degree vector, thus simultaneously modeling the number of edges (the l_1-norm) and the maximum degree (the l_{infty}-norm). We give precise upper bounds for all ranges of p and stretch t: we prove that the greedy (2k-1)-spanner has l_p norm of at most max(O(n), O(n^{{k+p}/{kp}})), and that this bound is tight (assuming the Erdős girth conjecture). We also study universal lower bounds, allowing us to give "generic" guarantees on the approximation ratio of the greedy algorithm which generalize and interpolate between the known approximations for the l_1 and l_{infty} norm. Finally, we show that at least in some situations, the l_p norm behaves fundamentally differently from l_1 or l_{infty}: there are regimes (p=2 and stretch 3 in particular) where the greedy spanner has a provably superior approximation to the generic guarantee.

Subject Classification

ACM Subject Classification
  • Theory of computation → Sparsification and spanners
Keywords
  • spanners
  • approximations

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Noga Alon, Yossi Azar, Gerhard J. Woeginger, and Tal Yadid. Approximation Schemes for Scheduling. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '97, 1997. Google Scholar
  2. Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discrete Comput. Geom., 9(1):81-100, 1993. URL: http://dx.doi.org/10.1007/BF02189308.
  3. Yossi Azar, Leah Epstein, Yossi Richter, and Gerhard J. Woeginger. All-Norm Approximation Algorithms. In Martti Penttonen and Erik Meineche Schmidt, editors, Algorithm Theory - SWAT 2002, 2002. Google Scholar
  4. Nikhil Bansal and Kirk Pruhs. Server Scheduling in the L_p Norm: A Rising Tide Lifts All Boat. In Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing, STOC '03, pages 242-250, 2003. Google Scholar
  5. Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, and Grigory Yaroslavtsev. Approximation algorithms for spanner problems and Directed Steiner Forest. Inf. Comput., 222:93-107, 2013. URL: http://dx.doi.org/10.1016/j.ic.2012.10.007.
  6. Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vijayaraghavan. Detecting high log-densities: an O(n^1/4)-approximation for densest k-subgraph. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 201-210. ACM, 2010. URL: http://dx.doi.org/10.1145/1806689.1806719.
  7. Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, and David P. Woodruff. Transitive-closure Spanners. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '09, pages 932-941, Philadelphia, PA, USA, 2009. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=1496770.1496871.
  8. Barun Chandra, Gautam Das, Giri Narasimhan, and José Soares. New Sparseness Results on Graph Spanners. In Proceedings of the Eighth Annual Symposium on Computational Geometry, SCG '92, pages 192-201, New York, NY, USA, 1992. ACM. URL: http://dx.doi.org/10.1145/142675.142717.
  9. Eden Chlamtác and Michael Dinitz. Lowest Degree k-Spanner: Approximation and Hardness. In Klaus Jansen, José D. P. Rolim, Nikhil R. Devanur, and Cristopher Moore, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014), volume 28 of Leibniz International Proceedings in Informatics (LIPIcs), pages 80-95, Dagstuhl, Germany, 2014. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.80.
  10. Eden Chlamtac, Michael Dinitz, and Robert Krauthgamer. Everywhere-Sparse Spanners via Dense Subgraphs. In Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, FOCS '12, pages 758-767, Washington, DC, USA, 2012. IEEE Computer Society. URL: http://dx.doi.org/10.1109/FOCS.2012.61.
  11. Eden Chlamtác, Michael Dinitz, and Yury Makarychev. Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 881-899. SIAM, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.56.
  12. Eden Chlamtác, Michael Dinitz, and Thomas Robinson. The Norms of Graph Spanners. CoRR, abs/1903.07418, 2019. URL: http://arxiv.org/abs/1903.07418.
  13. Eden Chlamtác and Pasin Manurangsi. Sherali-Adams Integrality Gaps Matching the Log-Density Threshold. In Eric Blais, Klaus Jansen, José D. P. Rolim, and David Steurer, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018, August 20-22, 2018 - Princeton, NJ, USA, volume 116 of LIPIcs, pages 10:1-10:19. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.10.
  14. Eden Chlamtác, Pasin Manurangsi, Dana Moshkovitz, and Aravindan Vijayaraghavan. Approximation Algorithms for Label Cover and The Log-Density Threshold. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 900-919. SIAM, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.57.
  15. Michael Dinitz, Guy Kortsarz, and Ran Raz. Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner. ACM Trans. Algorithms, 12(2):25:1-25:16, December 2015. URL: http://dx.doi.org/10.1145/2818375.
  16. Michael Dinitz and Robert Krauthgamer. Directed Spanners via Flow-based Linear Programs. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC '11, pages 323-332, New York, NY, USA, 2011. ACM. URL: http://dx.doi.org/10.1145/1993636.1993680.
  17. Michael Dinitz and Robert Krauthgamer. Fault-tolerant Spanners: Better and Simpler. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC '11, pages 169-178, New York, NY, USA, 2011. ACM. URL: http://dx.doi.org/10.1145/1993806.1993830.
  18. Michael Dinitz and Zeyu Zhang. Approximating Low-stretch Spanners. In Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '16, pages 821-840, Philadelphia, PA, USA, 2016. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=2884435.2884494.
  19. Paul Erdös. Extremal problems in graph theory, pages 29-36. Academia Praha, Czechoslovakia, 1964. Google Scholar
  20. Arnold Filtser and Shay Solomon. The Greedy Spanner is Existentially Optimal. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC '16, pages 9-17, 2016. Google Scholar
  21. Daniel Golovin, Anupam Gupta, Amit Kumar, and Kanat Tangwongsan. All-Norms and All-L_p-Norms Approximation Algorithms. In FSTTCS, volume 2 of LIPIcs, pages 199-210. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2008. Google Scholar
  22. Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu. A local search approximation algorithm for k-means clustering. Computational Geometry, 28(2):89-112, 2004. Special Issue on the 18th Annual Symposium on Computational Geometry - SoCG2002. URL: http://dx.doi.org/10.1016/j.comgeo.2004.03.003.
  23. Guy Kortsarz and David Peleg. Generating Low-Degree 2-Spanners. SIAM J. Comput., 27(5):1438-1456, 1998. URL: http://dx.doi.org/10.1137/S0097539794268753.
  24. S. Lloyd. Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2):129-137, March 1982. URL: http://dx.doi.org/10.1109/TIT.1982.1056489.
  25. Stefan Neuwirth. The size of bipartite graphs with girth eight. arXiv Mathematics e-prints, page math/0102210, February 2001. URL: http://arxiv.org/abs/math/0102210.
  26. David Peleg and Alejandro A. Schäffer. Graph spanners. Journal of Graph Theory, 13(1):99-116, 1989. URL: http://dx.doi.org/10.1002/jgt.3190130114.
  27. David Peleg and Jeffrey D. Ullman. An optimal synchronizer for the hypercube. SIAM J. Comput., 18:740-747, August 1989. URL: http://dx.doi.org/10.1137/0218050.
  28. Mikkel Thorup and Uri Zwick. Compact Routing Schemes. In Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA '01, pages 1-10, 2001. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact