Document Open Access Logo

Improved Weighted Additive Spanners

Authors Michael Elkin, Yuval Gitlitz, Ofer Neiman

PDF
Thumbnail PDF

File

LIPIcs.DISC.2021.21.pdf
  • Filesize: 0.73 MB
  • 15 pages

Document Identifiers

Author Details

Michael Elkin
  • Ben-Gurion University of the Negev, Beer Sheva, Israel
Yuval Gitlitz
  • Ben-Gurion University of the Negev, Beer Sheva, Israel
Ofer Neiman
  • Ben-Gurion University of the Negev, Beer Sheva, Israel

Funding

  • Elkin, Michael: ISF grant 2344/19
  • Gitlitz, Yuval: Partially supported by the Lynn and William Frankel Center for Computer Sciences and ISF grant 1817/17.
  • Neiman, Ofer: ISF grant 1817/17

Cite As Get BibTex

Michael Elkin, Yuval Gitlitz, and Ofer Neiman. Improved Weighted Additive Spanners. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.DISC.2021.21

Abstract

Graph spanners and emulators are sparse structures that approximately preserve distances of the original graph. While there has been an extensive amount of work on additive spanners, so far little attention was given to weighted graphs. Only very recently [Abu Reyan Ahmed et al., 2020] extended the classical +2 (respectively, +4) spanners for unweighted graphs of size O(n^{3/2}) (resp., O(n^{7/5})) to the weighted setting, where the additive error is +2W (resp., +4W). This means that for every pair u,v, the additive stretch is at most +2W_{u,v}, where W_{u,v} is the maximal edge weight on the shortest u-v path (weights are normalized so that the minimum edge weight is 1). In addition, [Abu Reyan Ahmed et al., 2020] showed a randomized algorithm yielding a +8W_{max} spanner of size O(n^{4/3}), here W_{max} is the maximum edge weight in the entire graph.
In this work we improve the latter result by devising a simple deterministic algorithm for a +(6+ε)W spanner for weighted graphs with size O(n^{4/3}) (for any constant ε > 0), thus nearly matching the classical +6 spanner of size O(n^{4/3}) for unweighted graphs. Furthermore, we show a +(2+ε)W subsetwise spanner of size O(n⋅√{|S|}), improving the +4W_{max} result of [Abu Reyan Ahmed et al., 2020] (that had the same size). We also show a simple randomized algorithm for a +4W emulator of size Õ(n^{4/3}).
In addition, we show that our technique is applicable for very sparse additive spanners, that have linear size. It is known that such spanners must suffer polynomially large stretch. For weighted graphs, we use a variant of our simple deterministic algorithm that yields a linear size +Õ(√n⋅ W) spanner, and we also obtain a tradeoff between size and stretch.
Finally, generalizing the technique of [D. Dor et al., 2000] for unweighted graphs, we devise an efficient randomized algorithm producing a +2W spanner for weighted graphs of size Õ(n^{3/2}) in Õ(n²) time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Sparsification and spanners
Keywords
  • Graph theory
  • Pure additive spanners

Metrics

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

Related Versions

References

  1. Amir Abboud and Greg Bodwin. The 4/3 additive spanner exponent is tight. J. ACM, 64(4):28:1-28:20, 2017. URL: https://doi.org/10.1145/3088511.
  2. Amir Abboud, Greg Bodwin, and Seth Pettie. A hierarchy of lower bounds for sublinear additive spanners. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’17, page 568–576, USA, 2017. Society for Industrial and Applied Mathematics. Google Scholar
  3. Abu Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Stephen G. Kobourov, and Richard Spence. Weighted additive spanners. In Isolde Adler and Haiko Müller, editors, Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Leeds, UK, June 24-26, 2020, Revised Selected Papers, volume 12301 of Lecture Notes in Computer Science, pages 401-413. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-60440-0_32.
  4. Donald Aingworth, Chandra Chekuri, Piotr Indyk, and Rajeev Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput., 28(4):1167-1181, 1999. URL: https://doi.org/10.1137/S0097539796303421.
  5. Ingo Althöfer, Gautam Das, David P. Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discret. Comput. Geom., 9:81-100, 1993. URL: https://doi.org/10.1007/BF02189308.
  6. Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie. New constructions of (alpha, beta)-spanners and purely additive spanners. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pages 672-681. SIAM, 2005. URL: http://dl.acm.org/citation.cfm?id=1070432.1070526.
  7. Greg Bodwin. Some general structure for extremal sparsification problems. CoRR, abs/2001.07741, 2020. URL: http://arxiv.org/abs/2001.07741.
  8. Greg Bodwin and Virginia Vassilevska Williams. Better distance preservers and additive spanners. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 855-872. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch61.
  9. Gregory Bodwin and Virginia Vassilevska Williams. Very sparse additive spanners and emulators. In Tim Roughgarden, editor, Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015, pages 377-382. ACM, 2015. URL: https://doi.org/10.1145/2688073.2688103.
  10. Béla Bollobás, Don Coppersmith, and Michael Elkin. Sparse distance preservers and additive spanners. SIAM J. Discret. Math., 19(4):1029-1055, 2005. URL: https://doi.org/10.1137/S0895480103431046.
  11. Shiri Chechik. New additive spanners. In Sanjeev Khanna, editor, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 498-512. SIAM, 2013. URL: https://doi.org/10.1137/1.9781611973105.36.
  12. D. Dor, S. Halperin, and U. Zwick. All-pairs almost shortest paths. SIAM J. Comput., 29:1740-1759, 2000. Google Scholar
  13. M. Elkin. Computing almost shortest paths. In Proc. 20th ACM Symp. on Principles of Distributed Computing, pages 53-62, 2001. Google Scholar
  14. M. Elkin and J. Zhang. Efficient algorithms for constructing (1+ε,β)-spanners in the distributed and streaming models. Distributed Computing, 18:375-385, 2006. Google Scholar
  15. Michael Elkin, Yuval Gitlitz, and Ofer Neiman. Almost shortest paths with near-additive error in weighted graphs. CoRR, abs/1907.11422, 2019. URL: http://arxiv.org/abs/1907.11422.
  16. Michael Elkin and Ofer Neiman. On efficient distributed construction of near optimal routing schemes. Distributed Comput., 31(2):119-137, 2018. URL: https://doi.org/10.1007/s00446-017-0304-4.
  17. Michael Elkin and Ofer Neiman. Hopsets with constant hopbound, and applications to approximate shortest paths. SIAM J. Comput., 48(4):1436-1480, 2019. URL: https://doi.org/10.1137/18M1166791.
  18. Michael Elkin and David Peleg. (1+epsilon, beta)-spanner constructions for general graphs. SIAM J. Comput., 33(3):608-631, 2004. URL: https://doi.org/10.1137/S0097539701393384.
  19. Mathias Bæk Tejs Knudsen. Additive spanners: A simple construction. In R. Ravi and Inge Li Gørtz, editors, Algorithm Theory - SWAT 2014 - 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings, volume 8503 of Lecture Notes in Computer Science, pages 277-281. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-08404-6_24.
  20. D. Peleg and A. Schäffer. Graph spanners. J. Graph Theory, 13:99-116, 1989. Google Scholar
  21. D. Peleg and E. Upfal. A tradeoff between size and efficiency for routing tables. J. of the ACM, 36:510-530, 1989. Google Scholar
  22. Seth Pettie. Low distortion spanners. ACM Transactions on Algorithms, 6(1), 2009. URL: https://doi.org/10.1145/1644015.1644022.
  23. M. Thorup and U. Zwick. Spanners and emulators with sublinear distance errors. In Proc. of Symp. on Discr. Algorithms, pages 802-809, 2006. Google Scholar
  24. 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, New York, NY, USA, 2001. ACM. URL: https://doi.org/10.1145/378580.378581.
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 About DROPS Imprint Privacy Contact