Document Open Access Logo

Constructing Light Spanners Deterministically in Near-Linear Time

Authors Stephen Alstrup, Søren Dahlgaard, Arnold Filtser, Morten Stöckel, Christian Wulff-Nilsen

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.4.pdf
  • Filesize: 0.57 MB
  • 15 pages

Document Identifiers

Author Details

Stephen Alstrup
  • University of Copenhagen, Denmark
Søren Dahlgaard
  • SupWiz, Copenhagen, Denmark
  • University of Copenhagen, Denmark
Arnold Filtser
  • Ben Gurion University of the Negev, Israel
Morten Stöckel
  • University of Copenhagen, Denmark
Christian Wulff-Nilsen
  • University of Copenhagen, Denmark

Funding

  • Alstrup, Stephen: Research partly supported by Innovationsfonden DK, DABAI (5153-00004A) and by VILLUM Foundation grant 16582, Basic Algorithms Research Copenhagen (BARC).
  • Dahlgaard, Søren: Research partly supported by Advanced Grant DFF-0602-02499B from the Danish Council for Independent Research.
  • Filtser, Arnold: Supported in part by ISF grant No. (1817/17) and by BSF grant No. 2015813.
  • Stöckel, Morten: Research partly supported by Villum Fonden.
  • Wulff-Nilsen, Christian: Research partly supported by the Starting Grant 7027-00050B from the Independent Research Fund Denmark under the Sapere Aude research career programme.

Acknowledgements

We are grateful to Michael Elkin, Ofer Neiman, and Sebastian Forster for fruitful discussions.

Cite As Get BibTex

Stephen Alstrup, Søren Dahlgaard, Arnold Filtser, Morten Stöckel, and Christian Wulff-Nilsen. Constructing Light Spanners Deterministically in Near-Linear Time. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ESA.2019.4

Abstract

Graph spanners are well-studied and widely used both in theory and practice. In a recent breakthrough, Chechik and Wulff-Nilsen [Shiri Chechik and Christian Wulff-Nilsen, 2018] improved the state-of-the-art for light spanners by constructing a (2k-1)(1+epsilon)-spanner with O(n^(1+1/k)) edges and O_epsilon(n^(1/k)) lightness. Soon after, Filtser and Solomon [Arnold Filtser and Shay Solomon, 2016] showed that the classic greedy spanner construction achieves the same bounds. The major drawback of the greedy spanner is its running time of O(mn^(1+1/k)) (which is faster than [Shiri Chechik and Christian Wulff-Nilsen, 2018]). This makes the construction impractical even for graphs of moderate size. Much faster spanner constructions do exist but they only achieve lightness Omega_epsilon(kn^(1/k)), even when randomization is used. 
The contribution of this paper is deterministic spanner constructions that are fast, and achieve similar bounds as the state-of-the-art slower constructions. Our first result is an O_epsilon(n^(2+1/k+epsilon')) time spanner construction which achieves the state-of-the-art bounds. Our second result is an O_epsilon(m + n log n) time construction of a spanner with (2k-1)(1+epsilon) stretch, O(log k * n^(1+1/k) edges and O_epsilon(log k * n^(1/k)) lightness. This is an exponential improvement in the dependence on k compared to the previous result with such running time. Finally, for the important special case where k=log n, for every constant epsilon>0, we provide an O(m+n^(1+epsilon)) time construction that produces an O(log n)-spanner with O(n) edges and O(1) lightness which is asymptotically optimal. This is the first known sub-quadratic construction of such a spanner for any k = omega(1).
To achieve our constructions, we show a novel deterministic incremental approximate distance oracle. Our new oracle is crucial in our construction, as known randomized dynamic oracles require the assumption of a non-adaptive adversary. This is a strong assumption, which has seen recent attention in prolific venues. Our new oracle allows the order of the edge insertions to not be fixed in advance, which is critical as our spanner algorithm chooses which edges to insert based on the answers to distance queries. We believe our new oracle is of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Sparsification and spanners
  • Theory of computation → Dynamic graph algorithms
Keywords
  • Spanners
  • Light Spanners
  • Efficient Construction
  • Deterministic Dynamic Distance Oracle

Metrics

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

Related Versions

References

  1. Stephen Alstrup, Søren Dahlgaard, Arnold Filtser, Morten Stöckel, and Christian Wulff-Nilsen. Constructing Light Spanners Deterministically in Near-Linear Time. CoRR, abs/1709.01960, 2017. URL: http://arxiv.org/abs/1709.01960.
  2. 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. URL: https://doi.org/10.1007/BF02189308.
  3. Baruch Awerbuch. Complexity of Network Synchronization. J. ACM, 32(4):804-823, October 1985. URL: https://doi.org/10.1145/4221.4227.
  4. Yair Bartal, Arnold Filtser, and Ofer Neiman. On notions of distortion and an almost minimum spanning tree with constant average distortion. Journal of Computer and System Sciences, 2019. URL: https://doi.org/10.1016/j.jcss.2019.04.006.
  5. 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. See also ICALP'03. Google Scholar
  6. Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. New deterministic approximation algorithms for fully dynamic matching. In Proc. 48th ACM Symposium on Theory of Computing (STOC), pages 398-411, 2016. Google Scholar
  7. Barun Chandra, Gautam Das, Giri Narasimhan, and José Soares. New Sparseness Results on Graph Spanners. In Proc. 8th ACM Symposium on Computational Geometry (SoCG), pages 192-201, 1992. Google Scholar
  8. Shiri Chechik. Compact Routing Schemes with Improved Stretch. In Proc.ACM Symposium on Principles of Distributed Computing (PODC), pages 33-41, 2013. Google Scholar
  9. Shiri Chechik. Approximate Distance Oracles with Constant Query Time. In Proc. 46th ACM Symposium on Theory of Computing (STOC), pages 654-663, 2014. Google Scholar
  10. Shiri Chechik. Approximate Distance Oracles with Improved Bounds. In Proc. 47th ACM Symposium on Theory of Computing (STOC), pages 1-10, 2015. Google Scholar
  11. Shiri Chechik and Christian Wulff-Nilsen. Near-Optimal Light Spanners. ACM Trans. Algorithms, 14(3):33:1-33:15, 2018. URL: https://doi.org/10.1145/3199607.
  12. Gautam Das and Giri Narasimhan. A Fast Algorithm for Constructing Sparse Euclidean Spanners. Int. J. Comput. Geometry Appl., 7(4):297-315, 1997. URL: https://doi.org/10.1142/S0218195997000193.
  13. Michael Elkin and Ofer Neiman. Efficient Algorithms for Constructing Very Sparse Spanners and Emulators. ACM Trans. Algorithms, 15(1):4:1-4:29, 2019. URL: https://doi.org/10.1145/3274651.
  14. Michael Elkin, Ofer Neiman, and Shay Solomon. Light Spanners. SIAM J. Discrete Math., 29(3):1312-1321, 2015. URL: https://doi.org/10.1137/140979538.
  15. Michael Elkin and Shay Solomon. Fast Constructions of Lightweight Spanners for General Graphs. ACM Transactions on Algorithms, 12(3):29:1-29:21, 2016. See also SODA'13. Google Scholar
  16. Paul Erdős. Extremal problems in graph theory. In Theory of Graphs and its Applications, pages 29-36, 1964. Google Scholar
  17. Shimon Even and Yossi Shiloach. An On-Line Edge-Deletion Problem. J. ACM, 28(1):1-4, 1981. Google Scholar
  18. Arthur M. Farley, Andrzej Proskurowski, Daniel Zappala, and Kurt Windisch. Spanners and message distribution in networks. Discrete Applied Mathematics, 137(2):159-171, 2004. Google Scholar
  19. Arnold Filtser and Shay Solomon. The Greedy Spanner is Existentially Optimal. In Proc. of the 2016 ACM Symposium on Principles of Distributed Computing (PODC), pages 9-17, 2016. Google Scholar
  20. Shay Halperin and Uri Zwick. Linear time deterministic algorithm for computing spanners for unweighted graphs, 1996. Google Scholar
  21. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization. SIAM Journal on Computing, 45(3):947-1006, 2016. See also FOCS'13. Google Scholar
  22. Ioannis Koutis and Shen Chen Xu. Simple Parallel and Distributed Algorithms for Spectral Graph Sparsification. TOPC, 3(2):14:1-14:14, 2016. URL: https://doi.org/10.1145/2948062.
  23. Gary L. Miller, Richard Peng, Adrian Vladu, and Shen Chen Xu. Improved Parallel Algorithms for Spanners and Hopsets. In Proc. 27th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 192-201, 2015. Google Scholar
  24. David Peleg and Alejandro A. Schäffer. Graph spanners. Journal of Graph Theory, 13(1):99-116, 1989. Google Scholar
  25. David Peleg and Jeffrey D. Ullman. An Optimal Synchronizer for the Hypercube. In Proc. 6thACM Symposium on Principles of Distributed Computing (PODC), pages 77-85, 1987. Google Scholar
  26. David Peleg and Eli Upfal. A Tradeoff Between Space and Efficiency for Routing Tables. In Proc 20th ACM Symposium on Theory of Computing (STOC), pages 43-52, 1988. Google Scholar
  27. Liam Roditty, Mikkel Thorup, and Uri Zwick. Deterministic Constructions of Approximate Distance Oracles and Spanners. In Proc. 32nd International Colloquium on Automata, Languages and Programming (ICALP), pages 261-272, 2005. Google Scholar
  28. Liam Roditty and Uri Zwick. On Dynamic Shortest Paths Problems. Algorithmica, 61(2):389-401, 2011. Google Scholar
  29. Liam Roditty and Uri Zwick. Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs. SIAM Journal on Computing, 41(3):670-683, 2012. See also FOCS'04. Google Scholar
  30. Mikkel Thorup and Uri Zwick. Compact Routing Schemes. In Proc. 13th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 1-10, 2001. Google Scholar
  31. Mikkel Thorup and Uri Zwick. Approximate Distance Oracles. Journal of the ACM, 52(1):1-24, January 2005. See also STOC'01. URL: https://doi.org/10.1145/1044731.1044732.
  32. Christian Wulff-Nilsen. Approximate Distance Oracles with Improved Preprocessing Time. In Proc. 23rd ACM/SIAM Symposium on Discrete Algorithms (SODA), pages 202-208, 2012. Google Scholar
  33. Christian Wulff-Nilsen. Approximate Distance Oracles with Improved Query Time. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 539-549, 2013. Google Scholar
  34. Christian Wulff-Nilsen. Fully-Dynamic Minimum Spanning Forest with Improved Worst-Case Update Time. CoRR, abs/1611.02864, 2016. To appear at STOC'17. URL: http://arxiv.org/abs/1611.02864.
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