Document Open Access Logo

Expander Decomposition in Dynamic Streams

Authors Arnold Filtser, Michael Kapralov, Mikhail Makarov

PDF

File

Thumbnail PDF
PDF
LIPIcs.ITCS.2023.50.pdf
  • Filesize: 0.63 MB
  • 13 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming models
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Sketching and sampling
Keywords
  • Streaming
  • expander decomposition
  • graph sparsifiers

Metrics

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

Abstract

In this paper we initiate the study of expander decompositions of a graph G = (V, E) in the streaming model of computation. The goal is to find a partitioning 𝒞 of vertices V such that the subgraphs of G induced by the clusters C ∈ 𝒞 are good expanders, while the number of intercluster edges is small. Expander decompositions are classically constructed by a recursively applying balanced sparse cuts to the input graph. In this paper we give the first implementation of such a recursive sparsest cut process using small space in the dynamic streaming model.
Our main algorithmic tool is a new type of cut sparsifier that we refer to as a power cut sparsifier - it preserves cuts in any given vertex induced subgraph (or, any cluster in a fixed partition of V) to within a (δ, ε)-multiplicative/additive error with high probability. The power cut sparsifier uses Õ(n/εδ) space and edges, which we show is asymptotically tight up to polylogarithmic factors in n for constant δ.

Cite As Get BibTex

Arnold Filtser, Michael Kapralov, and Mikhail Makarov. Expander Decomposition in Dynamic Streams. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 50:1-50:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ITCS.2023.50

Author Details

Arnold Filtser
  • Bar-Ilan University, Ramat-Gan, Israel
Michael Kapralov
  • EPFL, Lausanne, Switzerland
Mikhail Makarov
  • EPFL, Lausanne, Switzerland

Funding

  • Filtser, Arnold: Supported by the ISRAEL SCIENCE FOUNDATION (grant No. 1042/22).
  • Kapralov, Michael: Supported in part by ERC Starting Grant 759471.
  • Makarov, Mikhail: Supported by ERC Starting Grant 759471.

References

  1. 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 2012, Kyoto, Japan, January 17-19, 2012, pages 459-467, 2012. URL: https://doi.org/10.1137/1.9781611973099.40.
  2. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Graph sketches: sparsification, spanners, and subgraphs. In Michael Benedikt, Markus Krötzsch, and Maurizio Lenzerini, editors, Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2012, Scottsdale, AZ, USA, May 20-24, 2012, pages 5-14. ACM, 2012. URL: https://doi.org/10.1145/2213556.2213560.
  3. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Spectral sparsification in dynamic graph streams. In Prasad Raghavendra, Sofya Raskhodnikova, Klaus Jansen, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings, volume 8096 of Lecture Notes in Computer Science, pages 1-10. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-40328-6_1.
  4. Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan. Graph clustering using effective resistance. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, volume 94 of LIPIcs, pages 41:1-41:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ITCS.2018.41.
  5. Ingo Althöfer, Gautam Das, David P. Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discret. Comput. Geom., 9:81-100, 1993. URL: https://doi.org/10.1007/BF02189308.
  6. Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, and Qin Zhang. On sketching quadratic forms. In Madhu Sudan, editor, Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016, pages 311-319. ACM, 2016. URL: https://doi.org/10.1145/2840728.2840753.
  7. Sanjeev Arora, Boaz Barak, and David Steurer. Subexponential algorithms for unique games and related problems. J. ACM, 62(5):42:1-42:25, 2015. URL: https://doi.org/10.1145/2775105.
  8. Sepehr Assadi, Sanjeev Khanna, and Yang Li. On estimating maximum matching size in graph streams. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1723-1742. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974782.113.
  9. Sepehr Assadi, Sanjeev Khanna, Yang Li, and Grigory Yaroslavtsev. Maximum matchings in dynamic graph streams and the simultaneous communication model. 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 1345-1364. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch93.
  10. Nikhil Bansal, Ola Svensson, and Luca Trevisan. New notions and constructions of sparsification for graphs and hypergraphs. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 910-928. IEEE, 2019. Google Scholar
  11. 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. URL: https://doi.org/10.1002/rsa.20130.
  12. András A. Benczúr and David R. Karger. Approximating s-t minimum cuts in Õ(n^2) time. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 47-55, 1996. URL: https://doi.org/10.1145/237814.237827.
  13. Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak. Deterministic decremental reachability, scc, and shortest paths via directed expanders and congestion balancing. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1123-1134. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00108.
  14. Yi-Jun Chang, Seth Pettie, Thatchaphol Saranurak, and Hengjie Zhang. Near-optimal distributed triangle enumeration via expander decompositions. J. ACM, 68(3):21:1-21:36, 2021. URL: https://doi.org/10.1145/3446330.
  15. Yi-Jun Chang and Thatchaphol Saranurak. Improved distributed expander decomposition and nearly optimal triangle enumeration. In Peter Robinson and Faith Ellen, editors, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 66-73. ACM, 2019. URL: https://doi.org/10.1145/3293611.3331618.
  16. Yi-Jun Chang and Thatchaphol Saranurak. Deterministic distributed expander decomposition and routing with applications in distributed derandomization. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 377-388. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00043.
  17. Shiri Chechik. Approximate distance oracles with improved bounds. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 1-10. ACM, 2015. URL: https://doi.org/10.1145/2746539.2746562.
  18. Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. CoRR, abs/2203.00671, 2022. URL: https://doi.org/10.48550/arXiv.2203.00671.
  19. Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, and Junxing Wang. Graph sparsification, spectral sketches, and faster resistance computation, via short cycle decompositions. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 361-372. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/FOCS.2018.00042.
  20. Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, and Adrian Vladu. Almost-linear-time algorithms for markov chains and new spectral primitives for directed graphs. 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 410-419. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055463.
  21. P. Erdős. Extremal problems in graph theory. Theory of Graphs and Its Applications (Proc. Sympos. Smolenice), pages 29-36, 1964. see URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.210.7240.
  22. Manuel Fernandez, David P. Woodruff, and Taisuke Yasuda. Graph spanners in the message-passing model. In 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, pages 77:1-77:18, 2020. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.77.
  23. Arnold Filtser, Michael Kapralov, and Mikhail Makarov. Expander decomposition in dynamic streams, 2022. URL: https://doi.org/10.48550/ARXIV.2211.11384.
  24. Arnold Filtser, Michael Kapralov, and Navid Nouri. Graph spanners by sketching in dynamic streams and the simultaneous communication model. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 1894-1913, 2021. URL: https://doi.org/10.1137/1.9781611976465.113.
  25. Arnold Filtser and Shay Solomon. The greedy spanner is existentially optimal. SIAM J. Comput., 49(2):429-447, 2020. URL: https://doi.org/10.1137/18M1210678.
  26. Wai Shing Fung, Ramesh Hariharan, Nicholas J. A. Harvey, and Debmalya Panigrahi. A general framework for graph sparsification. SIAM J. Comput., 48(4):1196-1223, 2019. URL: https://doi.org/10.1137/16M1091666.
  27. Mohsen Ghaffari, Fabian Kuhn, and Hsin-Hao Su. Distributed MST and routing in almost mixing time. In Elad Michael Schiller and Alexander A. Schwarzmann, editors, Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages 131-140. ACM, 2017. URL: https://doi.org/10.1145/3087801.3087827.
  28. Oded Goldreich and Dana Ron. A sublinear bipartiteness tester for bounded degree graphs. Comb., 19(3):335-373, 1999. URL: https://doi.org/10.1007/s004930050060.
  29. Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak, and Zihan Tan. The expander hierarchy and its applications to dynamic graph algorithms. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 2212-2228. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.132.
  30. Sudipto Guha, Andrew McGregor, and David Tench. Vertex and hyperedge connectivity in dynamic graph streams. In Tova Milo and Diego Calvanese, editors, Proceedings of the 34th ACM Symposium on Principles of Database Systems, PODS 2015, Melbourne, Victoria, Australia, May 31 - June 4, 2015, pages 241-247. ACM, 2015. URL: https://doi.org/10.1145/2745754.2745763.
  31. Bernhard Haeupler, Harald Räcke, and Mohsen Ghaffari. Hop-constrained expander decompositions, oblivious routing, and distributed universal optimality. In Stefano Leonardi and Anupam Gupta, editors, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 1325-1338. ACM, 2022. URL: https://doi.org/10.1145/3519935.3520026.
  32. Arun Jambulapati and Aaron Sidford. Efficient Õ(n/ε) spectral sketches for the laplacian and its pseudoinverse. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2487-2503. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.159.
  33. Ravi Kannan, Santosh S. Vempala, and Adrian Vetta. On clusterings: Good, bad and spectral. J. ACM, 51(3):497-515, 2004. URL: https://doi.org/10.1145/990308.990313.
  34. Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford. Single pass spectral sparsification in dynamic streams. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 561-570. IEEE Computer Society, 2014. URL: https://doi.org/10.1109/FOCS.2014.66.
  35. Michael Kapralov, Aida Mousavifar, Cameron Musco, Christopher Musco, Navid Nouri, Aaron Sidford, and Jakab Tardos. Fast and space efficient spectral sparsification in dynamic streams. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1814-1833. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.111.
  36. Michael Kapralov and David P. Woodruff. Spanners and sparsifiers in dynamic streams. In ACM Symposium on Principles of Distributed Computing, PODC '14, Paris, France, July 15-18, 2014, pages 272-281, 2014. URL: https://doi.org/10.1145/2611462.2611497.
  37. Ken-ichi Kawarabayashi and Mikkel Thorup. Deterministic edge connectivity in near-linear time. J. ACM, 66(1):4:1-4:50, 2019. URL: https://doi.org/10.1145/3274663.
  38. Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 217-226. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973402.16.
  39. Jason Li and Thatchaphol Saranurak. Deterministic weighted expander decomposition in almost-linear time. CoRR, abs/2106.01567, 2021. URL: http://arxiv.org/abs/2106.01567.
  40. Andrew McGregor. Graph stream algorithms: A survey. SIGMOD Rec., 43(1):9-20, 2014. ICALP2004. URL: https://doi.org/10.1145/2627692.2627694.
  41. Andrew McGregor. Graph sketching and streaming: New approaches for analyzing massive graphs. In Pascal Weil, editor, Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Kazan, Russia, June 8-12, 2017, Proceedings, volume 10304 of Lecture Notes in Computer Science, pages 20-24. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-58747-9_4.
  42. Danupon Nanongkai and Thatchaphol Saranurak. Dynamic spanning forest with worst-case update time: adaptive, las vegas, and o(n^1/2-ε)-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 1122-1129. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055447.
  43. Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff-Nilsen. Dynamic minimum spanning forest with subpolynomial worst-case update time. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 950-961. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.92.
  44. Prasad Raghavendra and David Steurer. Graph expansion and the unique games conjecture. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 755-764. ACM, 2010. URL: https://doi.org/10.1145/1806689.1806792.
  45. Thatchaphol Saranurak and Di Wang. Expander decomposition and pruning: Faster, stronger, and simpler. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2616-2635. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.162.
  46. Daniel A. Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In László Babai, editor, Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pages 81-90. ACM, 2004. URL: https://doi.org/10.1145/1007352.1007372.
  47. Daniel A. Spielman and Shang-Hua Teng. Spectral sparsification of graphs. SIAM J. Comput., 40(4):981-1025, 2011. URL: https://doi.org/10.1137/08074489X.
  48. Daniel A. Spielman and Shang-Hua Teng. A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. SIAM J. Comput., 42(1):1-26, 2013. URL: https://doi.org/10.1137/080744888.
  49. Luca Trevisan. Approximation algorithms for unique games. Theory Comput., 4(1):111-128, 2008. URL: https://doi.org/10.4086/toc.2008.v004a005.
  50. Christian Wulff-Nilsen. Fully-dynamic minimum spanning forest with improved worst-case update 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 1130-1143. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055415.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact