Document Open Access Logo

New Additive Emulators

Authors Shimon Kogan, Merav Parter

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2023.85.pdf
  • Filesize: 0.82 MB
  • 17 pages

Document Identifiers

Author Details

Shimon Kogan
  • Weizmann Institute of Science, Rehovot, Israel
Merav Parter
  • Weizmann Institute of Science, Rehovot, Israel

Funding

This project is funded by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 949083), and by the Israeli Science Foundation (ISF), grant No. 2084/18.

Cite As Get BibTex

Shimon Kogan and Merav Parter. New Additive Emulators. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 85:1-85:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ICALP.2023.85

Abstract

For a given (possibly weighted) graph G = (V,E), an additive emulator H is a weighted graph in V × V that preserves the (all pairs) G-distances up to a small additive stretch. In their breakthrough result, [Abboud and Bodwin, STOC 2016] ruled out the possibility of obtaining o(n^{4/3})-size emulator with n^{o(1)} additive stretch. The focus of our paper is in the following question that has been explicitly stated in many of the prior work on this topic: 
What is the minimal additive stretch attainable with linear size emulators? 
The only known upper bound for this problem is given by an implicit construction of [Pettie, ICALP 2007] that provides a linear-size emulator with +Õ(n^{1/4}) stretch. No improvement on this problem has been shown since then. 
In this work we improve upon the long standing additive stretch of Õ(n^{1/4}), by presenting constructions of linear-size emulators with Õ(n^{0.222}) additive stretch. Our constructions improve the state-of-the-art size vs. stretch tradeoff in the entire regime. For example, for every ε > 1/7, we provide +n^{f(ε)} emulators of size Õ(n^{1+ε}), for f(ε) = 1/5-3ε/5. This should be compared with the current bound of f(ε) = 1/4-3ε/4 by [Pettie, ICALP 2007]. 
The new emulators are based on an extended and optimized toolkit for computing weighted additive emulators with sublinear distance error. Our key construction provides a weighted modification of the well-known Thorup and Zwick emulators [SODA 2006]. We believe that this TZ variant might be of independent interest, especially for providing improved stretch for distant pairs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • Spanners
  • Emulators
  • Distance Preservers

Metrics

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

References

  1. Amir Abboud and Greg Bodwin. The 4/3 additive spanner exponent is tight. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 351-361. ACM, 2016. Google Scholar
  2. Amir Abboud, Greg Bodwin, and Seth Pettie. A hierarchy of lower bounds for sublinear additive spanners. SIAM J. Comput., 47(6):2203-2236, 2018. Google Scholar
  3. Abu Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen G. Kobourov, and Richard Spence. Graph spanners: A tutorial review. Comput. Sci. Rev., 37:100253, 2020. Google Scholar
  4. 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. Google Scholar
  5. 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. Google Scholar
  6. Ingo Althöfer, Gautam Das, David P. Dobkin, and Deborah Joseph. Generating sparse spanners for weighted graphs. In John R. Gilbert and Rolf G. Karlsson, editors, SWAT 90, 2nd Scandinavian Workshop on Algorithm Theory, Bergen, Norway, July 11-14, 1990, Proceedings, volume 447 of Lecture Notes in Computer Science, pages 26-37. Springer, 1990. Google Scholar
  7. Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie. Additive spanners and (alpha, beta)-spanners. ACM Trans. Algorithms, 7(1):5:1-5:26, 2010. Google Scholar
  8. Greg Bodwin and Gary Hoppenworth. New additive spanner lower bounds by an unlayered obstacle product. CoRR, abs/2207.11832, 2022. URL: https://doi.org/10.48550/arXiv.2207.11832.
  9. 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. Google Scholar
  10. 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. Google Scholar
  11. Dorit Dor, Shay Halperin, and Uri Zwick. All pairs almost shortest paths. In 37th Annual Symposium on Foundations of Computer Science, FOCS '96, Burlington, Vermont, USA, 14-16 October, 1996, pages 452-461. IEEE Computer Society, 1996. Google Scholar
  12. Michael Elkin, Yuval Gitlitz, and Ofer Neiman. Improved weighted additive spanners. In Seth Gilbert, editor, 35th International Symposium on Distributed Computing, DISC 2021, October 4-8, 2021, Freiburg, Germany (Virtual Conference), volume 209 of LIPIcs, pages 21:1-21:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  13. Michael Elkin, Yuval Gitlitz, and Ofer Neiman. Almost shortest paths with near-additive error in weighted graphs. In Artur Czumaj and Qin Xin, editors, 18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022, June 27-29, 2022, Tórshavn, Faroe Islands, volume 227 of LIPIcs, pages 23:1-23:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. Google Scholar
  14. Michael Elkin and Shaked Matar. Ultra-sparse near-additive emulators. In Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen, editors, PODC '21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021, pages 235-246. ACM, 2021. Google Scholar
  15. Michael Elkin and David Peleg. (1+epsilon, beta)-spanner constructions for general graphs. In Jeffrey Scott Vitter, Paul G. Spirakis, and Mihalis Yannakakis, editors, Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pages 173-182. ACM, 2001. Google Scholar
  16. Shang-En Huang and Seth Pettie. Lower bounds on sparse spanners, emulators, and diameter-reducing shortcuts. SIAM J. Discret. Math., 35(3):2129-2144, 2021. URL: https://doi.org/10.1137/19M1306154.
  17. Kevin Lu, Virginia Vassilevska Williams, Nicole Wein, and Zixuan Xu. Better lower bounds for shortcut sets and additive spanners via an improved alternation product. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9-12, 2022, pages 3311-3331. SIAM, 2022. Google Scholar
  18. Seth Pettie. Low distortion spanners. In Lars Arge, Christian Cachin, Tomasz Jurdzinski, and Andrzej Tarlecki, editors, Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland, July 9-13, 2007, Proceedings, volume 4596 of Lecture Notes in Computer Science, pages 78-89. Springer, 2007. Google Scholar
  19. Mikkel Thorup and Uri Zwick. Spanners and emulators with sublinear distance errors. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006, pages 802-809. ACM Press, 2006. Google Scholar
  20. David P. Woodruff. Lower bounds for additive spanners, emulators, and more. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 389-398. IEEE Computer Society, 2006. 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 About DROPS Imprint Privacy Contact