Document Open Access Logo

Lowest Degree k-Spanner: Approximation and Hardness

Authors Eden Chlamtác, Michael Dinitz

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2014.80.pdf
  • Filesize: 0.51 MB
  • 16 pages

Document Identifiers

Author Details

Eden Chlamtác
Michael Dinitz

Cite AsGet BibTex

Eden Chlamtác and Michael Dinitz. Lowest Degree k-Spanner: Approximation and Hardness. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 80-95, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.80

Abstract

A k-spanner is a subgraph in which distances are approximately preserved, up to some given stretch factor k. We focus on the following problem: Given a graph and a value k, can we find a k-spanner that minimizes the maximum degree? While reasonably strong bounds are known for some spanner problems, they almost all involve minimizing the total number of edges. Switching the objective to the degree introduces significant new challenges, and currently the only known approximation bound is an O~(Delta^(3-2*sqrt(2)))-approximation for the special case when k = 2 [Chlamtac, Dinitz, Krauthgamer FOCS 2012] (where Delta is the maximum degree in the input graph). In this paper we give the first non-trivial algorithm and polynomial-factor hardness of approximation for the case of general k. Specifically, we give an LP-based O~(Delta^((1-1/k)^2) )-approximation and prove that it is hard to approximate the optimum to within Delta^Omega(1/k) when the graph is undirected, and to within Delta^Omega(1) when it is directed.
Keywords
  • Graph spanners
  • approximation algorithms
  • hardness of approximation

Metrics

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

References

  1. 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. Google Scholar
  2. Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie. Additive spanners and (α, β)-spanners. ACM Trans. Algorithms, 7(1):5:1-5:26, December 2010. Google Scholar
  3. Mohsen Bayati, Andrea Montanari, and Amin Saberi. Generating random graphs with large girth. In SODA'09, pages 566-575, 2009. Google Scholar
  4. Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, and Grigory Yaroslavtsev. Improved approximation for the directed spanner problem. In ICALP (1), pages 1-12, 2011. Google Scholar
  5. Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, and David P. Woodruff. Transitive-closure spanners. In SODA'09, pages 932-941, 2009. Google Scholar
  6. T.-H. Hubert Chan, Michael Dinitz, and Anupam Gupta. Spanners with slack. In Proceedings of the 14th Annual European Symposium on Algorithms, ESA, pages 196-207, 2006. Google Scholar
  7. Barun Chandra, Gautam Das, Giri Narasimhan, and José Soares. New sparseness results on graph spanners. International Journal of Computational Geometry and Applications, 5(1):125-144, 1995. Google Scholar
  8. S. Chechik, M. Langberg, David Peleg, and L. Roditty. Fault-tolerant spanners for general graphs. In STOC'09, pages 435-444, New York, NY, USA, 2009. ACM. Google Scholar
  9. Shiri Chechik. New additive spanners. In SODA'13, pages 498-512, 2013. Google Scholar
  10. Eden Chlamtáč, Michael Dinitz, and Robert Krauthgamer. Everywhere-sparse spanners via dense subgraphs. FOCS'12, 0:758-767, 2012. Google Scholar
  11. Michael Dinitz, Guy Kortsarz, and Ran Raz. Label cover instances with large girth and the hardness of approximating basic k-spanner. In ICALP'12, pages 290-301, Berlin, Heidelberg, 2012. Springer-Verlag. Google Scholar
  12. Michael Dinitz and Robert Krauthgamer. Directed spanners via flow-based linear programs. In STOC'11, pages 323-332, New York, NY, USA, 2011. ACM. Google Scholar
  13. Michael Dinitz and Robert Krauthgamer. Fault-tolerant spanners: Better and simpler. In PODC'11, pages 169-178, 2011. Google Scholar
  14. Yevgeniy Dodis and Sanjeev Khanna. Designing networks with bounded pairwise distance. In Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing, STOC'99, pages 750-759, New York, NY, USA, 1999. ACM. Google Scholar
  15. Michael Elkin and David Peleg. The hardness of approximating spanner problems. In STACS, pages 370-381, 2000. Google Scholar
  16. Michael Elkin and David Peleg. Strong inapproximability of the basic k-spanner problem. In ICALP, pages 636-647, 2000. Google Scholar
  17. Michael Elkin and David Peleg. Approximating k-spanner problems for k > 2. Theor. Comput. Sci., 337(1-3):249-277, 2005. Google Scholar
  18. Michael Elkin and Shay Solomon. Fast constructions of light-weight spanners for general graphs. In In Proc. of 24th SODA, pages 513-525, 2013. Google Scholar
  19. Guy Kortsarz. On the hardness of approximating spanners. Algorithmica, 30(3):432-450, 2001. Google Scholar
  20. Guy Kortsarz and David Peleg. Generating sparse 2-spanners. J. Algorithms, 17(2):222-236, 1994. Google Scholar
  21. Guy Kortsarz and David Peleg. Generating low-degree 2-spanners. SIAM J. Comput., 27(5):1438-1456, 1998. Google Scholar
  22. David Peleg and Alejandro A. Schäffer. Graph spanners. Journal of Graph Theory, 13(1):99-116, 1989. Google Scholar
  23. David Peleg and Jeffrey D. Ullman. An optimal synchronizer for the hypercube. SIAM J. Comput., 18(4):740-747, 1989. Google Scholar
  24. Mohit Singh and Lap Chi Lau. Approximating minimum bounded degree spanning trees to within one of optimal. In STOC'07, pages 661-670, 2007. Google Scholar
  25. Mikkel Thorup and Uri Zwick. Compact routing schemes. In SPAA'01, pages 1-10, New York, NY, USA, 2001. ACM. Google Scholar
  26. Mikkel Thorup and Uri Zwick. Approximate distance oracles. J. ACM, 52(1):1-24, January 2005. 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