Document Open Access Logo

The Sparsest Additive Spanner via Multiple Weighted BFS Trees

Authors Keren Censor-Hillel, Ami Paz, Noam Ravid

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2018.7.pdf
  • Filesize: 0.52 MB
  • 16 pages

Document Identifiers

Author Details

Keren Censor-Hillel
  • Department of Computer Science, Technion, Haifa, Israel
Ami Paz
  • IRIF, CNRS and Paris Diderot University, Paris, France
Noam Ravid
  • Department of Computer Science, Technion, Haifa, Israel

Funding

This project has received funding from the European Union’s Horizon 2020 Research And Innovation Programe under grant agreement no. 755839, and also partially supported by ISF individual research grant 1696/14. Ami Paz was supported by the Fondation Sciences Mathématiques de Paris (FSMP).

Cite As Get BibTex

Keren Censor-Hillel, Ami Paz, and Noam Ravid. The Sparsest Additive Spanner via Multiple Weighted BFS Trees. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.OPODIS.2018.7

Abstract

Spanners are fundamental graph structures that sparsify graphs at the cost of small stretch. In particular, in recent years, many sequential algorithms constructing additive all-pairs spanners were designed, providing very sparse small-stretch subgraphs. Remarkably, it was then shown that the known (+6)-spanner constructions are essentially the sparsest possible, that is, larger additive stretch cannot guarantee a sparser spanner, which brought the stretch-sparsity trade-off to its limit. Distributed constructions of spanners are also abundant. However, for additive spanners, while there were algorithms constructing (+2) and (+4)-all-pairs spanners, the sparsest case of (+6)-spanners remained elusive.
We remedy this by designing a new sequential algorithm for constructing a (+6)-spanner with the essentially-optimal sparsity of O~(n^{4/3}) edges. We then show a distributed implementation of our algorithm, answering an open problem in [Keren Censor{-}Hillel et al., 2016].
A main ingredient in our distributed algorithm is an efficient construction of multiple weighted BFS trees. A weighted BFS tree is a BFS tree in a weighted graph, that consists of the lightest among all shortest paths from the root to each node. We present a distributed algorithm in the CONGEST model, that constructs multiple weighted BFS trees in |S|+D-1 rounds, where S is the set of sources and D is the diameter of the network graph.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
  • Theory of computation → Sparsification and spanners
  • Theory of computation → Shortest paths
Keywords
  • Distributed graph algorithms
  • congest model
  • weighted BFS trees
  • 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. Error Amplification for Pairwise Spanner Lower Bounds. In 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 841-854, 2016. Google Scholar
  2. Amir Abboud and Greg Bodwin. The 4/3 Additive Spanner Exponent Is Tight. J. ACM, 64(4):28:1-28:20, 2017. Google Scholar
  3. Amir Abboud, Keren Censor-Hillel, and Seri Khoury. Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks. In 30th International Symposium on Distributed Computing, DISC, pages 29-42, 2016. Google Scholar
  4. Udit Agarwal, Vijaya Ramachandran, Valerie King, and Matteo Pontecorvi. A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in Õ(n^3/2) Rounds. In ACM Symposium on Principles of Distributed Computing, PODC, pages 199-205, 2018. Google Scholar
  5. Baruch Awerbuch. Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election and Related Problems. In ACM Symposium on Theory of Computing, STOC, pages 230-240, 1987. Google Scholar
  6. Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie. Additive spanners and (alpha, beta)-spanners. ACM Trans. Algorithms, 7(1):5, 2010. Google Scholar
  7. Surender Baswana and Sandeep Sen. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Struct. Algorithms, 30(4):532-563, 2007. Google Scholar
  8. Keren Censor-Hillel and Michal Dory. Distributed Spanner Approximation. In ACM Symposium on Principles of Distributed Computing, PODC, pages 139-148, 2018. Google Scholar
  9. Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, and Petar Maymounkov. Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance. In 44th Symposium on Theory of Computing Conference, STOC, pages 961-970, 2012. Google Scholar
  10. Keren Censor-Hillel, Telikepalli Kavitha, Ami Paz, and Amir Yehudayoff. Distributed Construction of Purely Additive Spanners. In 30th International Symposium on Distributed Computing, DISC, pages 129-142, 2016. Google Scholar
  11. Keren Censor-Hillel, Ami Paz, and Noam Ravid. The Sparsest Additive Spanner via Multiple Weighted BFS Trees. CoRR, abs/1811.01997, 2018. URL: http://arxiv.org/abs/1811.01997.
  12. Shiri Chechik. Compact routing schemes with improved stretch. In ACM Symposium on Principles of Distributed Computing, PODC, pages 33-41, 2013. Google Scholar
  13. Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. Distributed Verification and Hardness of Distributed Approximation. SIAM J. Comput., 41(5):1235-1265, 2012. Google Scholar
  14. Bilel Derbel and Cyril Gavoille. Fast deterministic distributed algorithms for sparse spanners. Theor. Comput. Sci., 399(1-2):83-100, 2008. Google Scholar
  15. Bilel Derbel, Cyril Gavoille, and David Peleg. Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time. In 21st International Symposium on Distributed Computing, DISC, pages 179-192, 2007. Google Scholar
  16. Bilel Derbel, Cyril Gavoille, David Peleg, and Laurent Viennot. On the locality of distributed sparse spanner construction. In 27th Annual ACM Symposium on Principles of Distributed Computing, PODC, pages 273-282, 2008. Google Scholar
  17. Bilel Derbel, Cyril Gavoille, David Peleg, and Laurent Viennot. Local Computation of Nearly Additive Spanners. In International Symposium on Distributed Computing, DISC, pages 176-190, 2009. Google Scholar
  18. Devdatt P. Dubhashi, Alessandro Mei, Alessandro Panconesi, Jaikumar Radhakrishnan, and Aravind Srinivasan. Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons. J. Comput. Syst. Sci., 71(4):467-479, 2005. Google Scholar
  19. Michael Elkin. Computing almost shortest paths. ACM Trans. Algorithms, 1(2):283-323, 2005. Google Scholar
  20. Michael Elkin. Distributed exact shortest paths in sublinear time. In ACM SIGACT Symposium on Theory of Computing, STOC, pages 757-770, 2017. Google Scholar
  21. Michael Elkin and Ofer Neiman. Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS, pages 128-137, 2016. Google Scholar
  22. Michael Elkin and Jian Zhang. Efficient algorithms for constructing (1+ε, β)-spanners in the distributed and streaming models. Distributed Computing, 18(5):375-385, 2006. Google Scholar
  23. Robert G. Gallager, Pierre A. Humblet, and Philip M. Spira. A Distributed Algorithm for Minimum-Weight Spanning Trees. ACM Trans. Program. Lang. Syst., 5(1):66-77, 1983. Google Scholar
  24. Mohsen Ghaffari and Fabian Kuhn. Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set. In International Symposium on Distributed Computing, DISC, volume 121 of LIPIcs, pages 29:1-29:17, 2018. Google Scholar
  25. Mohsen Ghaffari and Jason Li. Improved distributed algorithms for exact shortest paths. In SIGACT Symposium on Theory of Computing, STOC, pages 431-444, 2018. Google Scholar
  26. Ofer Grossman and Merav Parter. Improved Deterministic Distributed Construction of Spanners. In 31st International Symposium on Distributed Computing, DISC, pages 24:1-24:16, 2017. Google Scholar
  27. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In ACM SIGACT Symposium on Theory of Computing, STOC, pages 489-498, 2016. Google Scholar
  28. Stephan Holzer. Personal communication. Google Scholar
  29. Stephan Holzer, David Peleg, Liam Roditty, and Roger Wattenhofer. Distributed 3/2-Approximation of the Diameter. In 28th International Symposium on Distributed Computing, DISC, pages 562-564, 2014. Google Scholar
  30. Stephan Holzer and Roger Wattenhofer. Optimal distributed all pairs shortest paths and applications. In ACM Symposium on Principles of Distributed Computing, PODC, pages 355-364, 2012. Google Scholar
  31. Chien-Chung Huang, Danupon Nanongkai, and Thatchaphol Saranurak. Distributed Exact Weighted All-Pairs Shortest Paths in Õ(n^5/4) Rounds. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 168-179, 2017. Google Scholar
  32. Telikepalli Kavitha. New Pairwise Spanners. In 32nd International Symposium on Theoretical Aspects of Computer Science, STACS, pages 513-526, 2015. Google Scholar
  33. Mathias Bæk Tejs Knudsen. Additive Spanners: A Simple Construction. In 14th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT, pages 277-281, 2014. Google Scholar
  34. Christoph Lenzen, Boaz Patt-Shamir, and David Peleg. Distributed distance computation and routing with small messages. Distributed Computing, pages 1-25, 2018. Google Scholar
  35. Christoph Lenzen and David Peleg. Efficient distributed source detection with limited bandwidth. In ACM Symposium on Principles of Distributed Computing, PODC, pages 375-382, 2013. Google Scholar
  36. Zvi Lotker, Boaz Patt-Shamir, and Seth Pettie. Improved Distributed Approximate Matching. J. ACM, 62(5):38:1-38:17, 2015. Google Scholar
  37. Danupon Nanongkai. Distributed approximation algorithms for weighted shortest paths. In Symposium on Theory of Computing, STOC, pages 565-573, 2014. Google Scholar
  38. Merav Parter. Vertex fault tolerant additive spanners. Distributed Computing, 30(5):357-372, 2017. Google Scholar
  39. Merav Parter and Eylon Yogev. Congested Clique Algorithms for Graph Spanners. In International Symposium on Distributed Computing, DISC, volume 121 of LIPIcs, pages 40:1-40:18, 2018. Google Scholar
  40. David Peleg. Distributed Computing: A Locality-Sensitive Approach. Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, 2000. Google Scholar
  41. David Peleg and Alejandro A. Schäffer. Graph spanners. Journal of Graph Theory, 13(1):99-116, 1989. Google Scholar
  42. David Peleg and Jeffrey D. Ullman. An Optimal Synchronizer for the Hypercube. SIAM J. Comput., 18(4):740-747, 1989. Google Scholar
  43. David Peleg and Eli Upfal. A trade-off between space and efficiency for routing tables. J. ACM, 36(3):510-530, 1989. Google Scholar
  44. Seth Pettie. Distributed algorithms for ultrasparse spanners and linear size skeletons. Distributed Computing, 22(3):147-166, 2010. Google Scholar
  45. Mikkel Thorup and Uri Zwick. Compact routing schemes. In ACM Symposium on Parallelism in Algorithms and Architectures, SPAA, pages 1-10, 2001. Google Scholar
  46. David P. Woodruff. Additive Spanners in Nearly Quadratic Time. In 37th International Colloquium on Automata, Languages and Programming, ICALP, pages 463-474, 2010. 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