Document Open Access Logo

An Improved Random Shift Algorithm for Spanners and Low Diameter Decompositions

Authors Sebastian Forster , Martin Grösbacher, Tijn de Vos

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2021.16.pdf
  • Filesize: 0.7 MB
  • 17 pages

Document Identifiers

Author Details

Sebastian Forster
  • University of Salzburg, Austria
Martin Grösbacher
  • University of Salzburg, Austria
Tijn de Vos
  • University of Salzburg, Austria

Funding

Supported by the Austrian Science Fund (FWF): P 32863-N.

Acknowledgements

The first author would like to thank Merav Parter for mentioning that there was still some room for improvement in the spanner construction.

Cite As Get BibTex

Sebastian Forster, Martin Grösbacher, and Tijn de Vos. An Improved Random Shift Algorithm for Spanners and Low Diameter Decompositions. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.OPODIS.2021.16

Abstract

Spanners have been shown to be a powerful tool in graph algorithms. Many spanner constructions use a certain type of clustering at their core, where each cluster has small diameter and there are relatively few spanner edges between clusters. In this paper, we provide a clustering algorithm that, given k ≥ 2, can be used to compute a spanner of stretch 2k-1 and expected size O(n^{1+1/k}) in k rounds in the CONGEST model. This improves upon the state of the art (by Elkin, and Neiman [TALG'19]) by making the bounds on both running time and stretch independent of the random choices of the algorithm, whereas they only hold with high probability in previous results. Spanners are used in certain synchronizers, thus our improvement directly carries over to such synchronizers. Furthermore, for keeping the total number of inter-cluster edges small in low diameter decompositions, our clustering algorithm provides the following guarantees. Given β ∈ (0,1], we compute a low diameter decomposition with diameter bound O((log n)/β) such that each edge e ∈ E is an inter-cluster edge with probability at most β⋅ w(e) in O((log n)/β) rounds in the CONGEST model. Again, this improves upon the state of the art (by Miller, Peng, and Xu [SPAA'13]) by making the bounds on both running time and diameter independent of the random choices of the algorithm, whereas they only hold with high probability in previous results.

Subject Classification

ACM Subject Classification
  • Theory of computation → Sparsification and spanners
  • Theory of computation → Distributed algorithms
Keywords
  • Spanner
  • low diameter decomposition
  • synchronizer
  • distributed graph algorithms

Metrics

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

Related Versions

References

  1. Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan. Graph clustering using effective resistance. In Proc. of the Innovations in Theoretical Computer Science Conference (ITCS), pages 41:1-41:16, 2018. Google Scholar
  2. Noga Alon, Richard M Karp, David Peleg, and Douglas West. A graph-theoretic game and its application to the k-server problem. SIAM Journal on Computing, 24(1):78-100, 1995. Google Scholar
  3. Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discrete & Computational Geometry, 9(1):81-100, 1993. Google Scholar
  4. Baruch Awerbuch. Complexity of network synchronization. Journal of the ACM, 32(4):804-823, 1985. Google Scholar
  5. Baruch Awerbuch, Bonnie Berger, Lenore Cowen, and David Peleg. Near-linear cost sequential and distributed constructions of sparse neighborhood covers. In Proc. of the Conference on Foundations of Computer Science (FOCS), pages 638-647, 1993. Google Scholar
  6. Baruch Awerbuch, Andrew V Goldberg, Michael Luby, and Serge A Plotkin. Network decomposition and locality in distributed computation. In Proc. of the Conference on Foundations of Computer Science (FOCS), volume 30, pages 364-369, 1989. Google Scholar
  7. Baruch Awerbuch, Boaz Patt-Shamir, David Peleg, and Michael Saks. Adapting to asynchronous dynamic networks. In Proc. of the Symposium on Theory of Computing (STOC), pages 557-570, 1992. Google Scholar
  8. Baruch Awerbuch and David Peleg. Network synchronization with polylogarithmic overhead. In Proc, of the Symposium on Foundations of Computer Science (FOCS), pages 514-522, 1990. Google Scholar
  9. Yair Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Proc. of the Conference on Foundations of Computer Science (FOCS), pages 184-193, 1996. Google Scholar
  10. Yair Bartal. On approximating arbitrary metrices by tree metrics. In Proc. of the Symposium on Theory of Computing (STOC), pages 161-168, 1998. Google Scholar
  11. Surender Baswana and Sandeep Sen. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Structures & Algorithms, 30(4):532-563, 2007. Google Scholar
  12. Keren Censor-Hillel, Bernhard Haeupler, Jonathan Kelner, and Petar Maymounkov. Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance. In Proc. of the Symposium on Theory of Computing (STOC), pages 961-970, 2012. Google Scholar
  13. Yi-Jun Chang, Seth Pettie, and Hengjie Zhang. Distributed triangle detection via expander decomposition. In Proc. of the Symposium on Discrete Algorithms (SODA), pages 821-840, 2019. Google Scholar
  14. Yi-Jun Chang and Thatchaphol Saranurak. Deterministic distributed expander decomposition and routing with applications in distributed derandomization. In Proc. of the Symposium on Foundations of Computer Science (FOCS), pages 377-388, 2020. Google Scholar
  15. Edith Cohen. Polylog-time and near-linear work approximation scheme for undirected shortest paths. In Proc. of the Symposium on Theory of Computing (STOC), pages 16-26, 1994. Google Scholar
  16. Edith Cohen. Fast algorithms for constructing t-spanners and paths with stretch t. SIAM Journal on Computing, 28(1):210-236, 1998. Google Scholar
  17. Michael Elkin and Ofer Neiman. Efficient algorithms for constructing very sparse spanners and emulators. ACM Transactions on Algorithms (TALG), 15, 2019. Google Scholar
  18. Arnold Filtser and Shay Solomon. The greedy spanner is existentially optimal. In Proc. of the Symposium on Principles of Distributed Computing (PODC), pages 9-17, 2016. Google Scholar
  19. Sebastian Forster and Gramoz Goranci. Dynamic low-stretch trees via dynamic low-diameter decompositions. In Proc. of the Symposium on Theory of Computing (STOC), pages 377-388, New York, NY, USA, 2019. Google Scholar
  20. Mohsen Ghaffari and Fabian Kuhn. Derandomizing distributed algorithms with small messages: Spanners and dominating set. In Proc. of the Symposium on Distributed Computing (DISC), pages 29:1-29:17, 2018. Google Scholar
  21. Joseph Gil, Yossi Matias, and Uzi Vishkin. Towards a theory of nearly constant time parallel algorithms. In Proc. of the Symposium of Foundations of Computer Science (FOCS), pages 698-710, 1991. Google Scholar
  22. Oded Goldreich and Dana Ron. A sublinear bipartiteness tester for bounded degree graphs. Combinatorica, 19(3):335-373, 1999. Google Scholar
  23. Shay Halperin and Uri Zwick. Personal communication, 1993. Google Scholar
  24. Ravi Kannan, Santosh Vempala, and Adrian Vetta. On clusterings: Good, bad and spectral. Journal of the ACM, 51(3):497-515, 2004. Google Scholar
  25. Philip N Klein and Sairam Subramanian. A randomized parallel algorithm for single-source shortest paths. Journal of Algorithms, 25(2):205-220, 1997. Google Scholar
  26. Ajay D Kshemkalyani and Mukesh Singhal. Distributed computing: principles, algorithms, and systems. Cambridge University Press, 2011. Google Scholar
  27. Tom Leighton and Satish Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM, 46(6):787-832, 1999. Google Scholar
  28. Nathan Linial and Michael Saks. Low diameter graph decompositions. Combinatorica, 13(4):441-454, 1993. Google Scholar
  29. Nancy A Lynch. Distributed algorithms. Elsevier, 1996. Google Scholar
  30. Gary L Miller, Richard Peng, Adrian Vladu, and Shen Chen Xu. Improved parallel algorithms for spanners and hopsets. In Proc. Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 192-201, 2015. Google Scholar
  31. Gary L Miller, Richard Peng, and Shen Xu. Parallel graph decompositions using random shifts. Proc. of the Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 196-203, 2013. Google Scholar
  32. David Peleg. Proximity-preserving labeling schemes. Journal of Graph Theory, 33(3):167-176, 2000. Google Scholar
  33. David Peleg and Eli Upfal. A trade-off between space and efficiency for routing tables. Journal of the ACM, 36(3):510-530, 1989. Google Scholar
  34. Liam Roditty and Uri Zwick. On dynamic shortest paths problems. In Proc. of the European Symposium on Algorithms (ESA), pages 580-591, 2004. Google Scholar
  35. Thatchaphol Saranurak and Di Wang. Expander decomposition and pruning: Faster, stronger, and simpler. In Proc. of the Symposium on Discrete Algorithms (SODA), pages 2616-2635, 2019. Google Scholar
  36. Daniel A Spielman and Shang-Hua Teng. Spectral sparsification of graphs. SIAM Journal on Computing, 40(4):981-1025, 2011. Google Scholar
  37. Mikkel Thorup. Undirected single-source shortest paths with positive integer weights in linear time. Journal of the ACM, 46(3):362-394, 1999. Google Scholar
  38. Mikkel Thorup and Uri Zwick. Approximate distance oracles. Journal of the ACM, 52(1):1-24, 2005. Google Scholar
  39. Shen Chen Xu. Exponential Start Time Clustering and its Applications in Spectral Graph Theory. PhD thesis, Carnegie Mellon University, Pittsburgh, 2017. 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