(1+ε)-Approximate Shortest Paths in Dynamic Streams

Authors Michael Elkin , Chhaya Trehan



PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.51.pdf
  • Filesize: 0.9 MB
  • 23 pages

Document Identifiers

Author Details

Michael Elkin
  • Ben-Gurion University of the Negev, Beer-Sheva, Israel
Chhaya Trehan
  • London School of Economics & Political Science, UK

Cite AsGet BibTex

Michael Elkin and Chhaya Trehan. (1+ε)-Approximate Shortest Paths in Dynamic Streams. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 51:1-51:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.51

Abstract

Computing approximate shortest paths in the dynamic streaming setting is a fundamental challenge that has been intensively studied. Currently existing solutions for this problem either build a sparse multiplicative spanner of the input graph and compute shortest paths in the spanner offline, or compute an exact single source BFS tree. Solutions of the first type are doomed to incur a stretch-space tradeoff of 2κ-1 versus n^{1+1/κ}, for an integer parameter κ. (In fact, existing solutions also incur an extra factor of 1+ε in the stretch for weighted graphs, and an additional factor of log^{O(1)}n in the space.) The only existing solution of the second type uses n^{1/2 - O(1/κ)} passes over the stream (for space O(n^{1+1/κ})), and applies only to unweighted graphs. In this paper we show that (1+ε)-approximate single-source shortest paths can be computed with Õ(n^{1+1/κ}) space using just constantly many passes in unweighted graphs, and polylogarithmically many passes in weighted graphs. Moreover, the same result applies for multi-source shortest paths, as long as the number of sources is O(n^{1/κ}). We achieve these results by devising efficient dynamic streaming constructions of (1 + ε, β)-spanners and hopsets. On our way to these results, we also devise a new dynamic streaming algorithm for the 1-sparse recovery problem. Even though our algorithm for this task is slightly inferior to the existing algorithms of [S. Ganguly, 2007; Graham Cormode and D. Firmani, 2013], we believe that it is of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming models
  • Theory of computation → Streaming, sublinear and near linear time algorithms
  • Theory of computation → Shortest paths
  • Theory of computation → Sparsification and spanners
Keywords
  • Shortest Paths
  • Dynamic Streams
  • Approximate Distances
  • Spanners
  • Hopsets

Metrics

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

References

  1. Amir Abboud and Greg Bodwin. The 4/3 additive spanner exponent is tight. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC '16, pages 351-361, New York, NY, USA, 2016. Association for Computing Machinery. URL: https://doi.org/10.1145/2897518.2897555.
  2. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Analyzing graph structure via linear measurements. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '12, pages 459-467, USA, 2012. Society for Industrial and Applied Mathematics. Google Scholar
  3. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Graph sketches: Sparsification, spanners, and subgraphs. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS'12, pages 5-14, New York, NY, USA, 2012. Association for Computing Machinery. URL: https://doi.org/10.1145/2213556.2213560.
  4. Ingo Althofer, Gautam Das, David Dobkin, and Deborah A Joseph. Generating sparse spanners for weighted graphs. Technical report, University of Wisconsin-Madison Department of Computer Sciences, 1989. Google Scholar
  5. Khanh Do Ba, Piotr Indyk, Eric Price, and David P. Woodruff. Lower bounds for sparse recovery. In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 1190-1197. SIAM, 2010. URL: https://doi.org/10.1137/1.9781611973075.95.
  6. Antal Balog and Imre Bárány. On the convex hull of the integer points in a disc. In Proceedings of the Seventh Annual Symposium on Computational Geometry, pages 162-165, New York, NY, USA, 1991. Association for Computing Machinery. URL: https://doi.org/10.1145/109648.109666.
  7. Surender Baswana. Streaming algorithm for graph spanners - single pass and constant processing time per edge. Information Processing Letters, 106(3):110-114, 2008. URL: https://doi.org/10.1016/j.ipl.2007.11.001.
  8. J.Lawrence Carter and Mark N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18(2):143-154, 1979. URL: https://doi.org/10.1016/0022-0000(79)90044-8.
  9. Yi-Jun Chang, Martin Farach-Colton, Tsan-sheng Hsu, and Meng-Tsung Tsai. Streaming complexity of spanning tree computation. In Christophe Paul and Markus Bläser, editors, 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France, volume 154 of LIPIcs, pages 34:1-34:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.STACS.2020.34.
  10. Edith Cohen. Polylog-time and near-linear work approximation scheme for undirected shortest paths. In STOC '94, 1994. Google Scholar
  11. Graham Cormode and D. Firmani. A unifying framework for ?0-sampling algorithms. Distributed and Parallel Databases, 32:315-335, 2013. Google Scholar
  12. Michael Elkin. Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. ACM Trans. Algorithms, 7(2), March 2011. URL: https://doi.org/10.1145/1921659.1921666.
  13. Michael Elkin. Distributed exact shortest paths in sublinear time. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 757-770. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055452.
  14. Michael Elkin, Yuval Gitlitz, and Ofer Neiman. Improved weighted additive spanners. CoRR, abs/2008.09877, 2020. URL: http://arxiv.org/abs/2008.09877.
  15. Michael Elkin and Ofer Neiman. Efficient algorithms for constructing very sparse spanners and emulators. ACM Trans. Algorithms, 15(1), November 2018. URL: https://doi.org/10.1145/3274651.
  16. Michael Elkin and Ofer Neiman. Hopsets with constant hopbound, and applications to approximate shortest paths. SIAM Journal on Computing, 48(4):1436-1480, 2019. URL: https://doi.org/10.1137/18M1166791.
  17. Michael Elkin and Ofer Neiman. Near-additive spanners and near-exact hopsets, A unified view. Bull. EATCS, 130, 2020. URL: http://bulletin.eatcs.org/index.php/beatcs/article/view/608/624.
  18. Michael Elkin and David Peleg. (1+ε, β)-spanner constructions for general graphs. In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, STOC '01, pages 173-182, New York, NY, USA, 2001. Association for Computing Machinery. URL: https://doi.org/10.1145/380752.380797.
  19. Michael Elkin and Shay Solomon. Fast constructions of light-weight spanners for general graphs. 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 513-525. SIAM, 2013. URL: https://doi.org/10.1137/1.9781611973105.37.
  20. Michael Elkin and Chhaya Trehan. dollar(1+ε)dollar-approximate shortest paths in dynamic streams. CoRR, abs/2107.13309, 2021. URL: http://arxiv.org/abs/2107.13309.
  21. Michael Elkin and Jian Zhang. Efficient algorithms for constructing (1+ε, β)-spanners in the distributed and streaming models. Distributed Computing, 18(5):375-385, 2006. URL: https://doi.org/10.1007/s00446-005-0147-2.
  22. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. On graph problems in a semi-streaming model. In Josep Díaz, Juhani Karhumäki, Arto Lepistö, and Donald Sannella, editors, Automata, Languages and Programming, pages 531-543, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. Google Scholar
  23. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. Graph distances in the data-stream model. SIAM Journal on Computing, 38(5):1709-1727, 2009. URL: https://doi.org/10.1137/070683155.
  24. Manuel Fernandez, David P. Woodruff, and Taisuke Yasuda. Graph spanners in the message-passing model. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of LIPIcs, pages 77:1-77:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.77.
  25. Arnold Filtser, Michael Kapralov, and Navid Nouri. Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model, pages 1894-1913. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.113.
  26. S. Ganguly. Counting distinct items over update streams. Theor. Comput. Sci., 378:211-222, 2007. Google Scholar
  27. David Gibb, Bruce M. Kapron, Valerie King, and Nolan Thorn. Dynamic graph connectivity with improved worst case update time and sublinear space. CoRR, abs/1509.06464, 2015. URL: http://arxiv.org/abs/1509.06464.
  28. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Improved algorithms for decremental single-source reachability on directed graphs. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming, pages 725-736, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg. Google Scholar
  29. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC '16, page 489?498, New York, NY, USA, 2016. Association for Computing Machinery. URL: https://doi.org/10.1145/2897518.2897638.
  30. Piotr Indyk, Eric Price, and David P. Woodruff. On the power of adaptivity in sparse recovery. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 285-294. IEEE Computer Society, 2011. URL: https://doi.org/10.1109/FOCS.2011.83.
  31. Vojtěch Jarník. Über die gitterpunkte auf konvexen kurven. Mathematische Zeitschrift, 24:500-518, 1926. Google Scholar
  32. Michael Kapralov and David Woodruff. Spanners and sparsifiers in dynamic streams. In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, PODC '14, pages 272-281, New York, NY, USA, 2014. Association for Computing Machinery. URL: https://doi.org/10.1145/2611462.2611497.
  33. Valerie King, Shay Kutten, and Mikkel Thorup. Construction and impromptu repair of an MST in a distributed network with o(m) communication. CoRR, abs/1502.03320, 2015. URL: http://arxiv.org/abs/1502.03320.
  34. Philip N Klein and Sairam Subramanian. A randomized parallel algorithm for single-source shortest paths. Journal of Algorithms, 25(2):205-220, 1997. URL: https://doi.org/10.1006/jagm.1997.0888.
  35. Felix Lazebnik and Vasiliy A. Ustimenko. Some algebraic constructions of dense graphs of large girth and of large size. In Joel Friedman, editor, Expanding Graphs, Proceedings of a DIMACS Workshop, Princeton, New Jersey, USA, May 11-14, 1992, volume 10 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 75-93. DIMACS/AMS, 1992. URL: https://doi.org/10.1090/dimacs/010/07.
  36. Andrew McGregor. Graph stream algorithms: A survey. SIGMOD Rec., 43(1):9-20, May 2014. URL: https://doi.org/10.1145/2627692.2627694.
  37. Morteza Monemizadeh and David P. Woodruff. 1-pass relative-error l_p-sampling with applications. In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 1143-1160. SIAM, 2010. URL: https://doi.org/10.1137/1.9781611973075.92.
  38. David Peleg and Alejandro A. Schaffer. Graph spanners. Journal of Graph Theory, 13(1):99-116, 1989. URL: https://doi.org/10.1002/jgt.3190130114.
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