Document Open Access Logo

Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player

Authors Daniel Agassy, Dani Dorfman, Haim Kaplan

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2023.9.pdf
  • Filesize: 0.79 MB
  • 20 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • Exapander Decomposition
  • Cut-Matching Game

Metrics

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

Abstract

A (ϕ,ε)-expander decomposition of a graph G (with n vertices and m edges) is a partition of V into clusters V₁,…,V_k with conductance Φ(G[V_i]) ≥ ϕ, such that there are at most ε m inter-cluster edges. Such a decomposition plays a crucial role in many graph algorithms. We give a randomized Õ(m/ϕ) time algorithm for computing a (ϕ, ϕlog²n)-expander decomposition. This improves upon the (ϕ, ϕlog³n)-expander decomposition also obtained in Õ(m/ϕ) time by [Saranurak and Wang, SODA 2019] (SW) and brings the number of inter-cluster edges within logarithmic factor of optimal. 
One crucial component of SW’s algorithm is a non-stop version of the cut-matching game of [Khandekar, Rao, Vazirani, JACM 2009] (KRV): The cut player does not stop when it gets from the matching player an unbalanced sparse cut, but continues to play on a trimmed part of the large side. The crux of our improvement is the design of a non-stop version of the cleverer cut player of [Orecchia, Schulman, Vazirani, Vishnoi, STOC 2008] (OSVV). The cut player of OSSV uses a more sophisticated random walk, a subtle potential function, and spectral arguments. Designing and analysing a non-stop version of this game was an explicit open question asked by SW.

Cite As Get BibTex

Daniel Agassy, Dani Dorfman, and Haim Kaplan. Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 9:1-9:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ICALP.2023.9

Author Details

Daniel Agassy
  • Tel Aviv University, Israel
Dani Dorfman
  • Tel Aviv University, Israel
Haim Kaplan
  • Tel Aviv University, Israel

Funding

Israel science foundation (ISF) grant 1595/19, Israel science foundation (ISF) grant 2854/20, and the Blavatnik research foundation.

References

  1. Daniel Agassy, Dani Dorfman, and Haim Kaplan. Expander decomposition with fewer inter-cluster edges using a spectral cut player. arXiv preprint, 2022. URL: https://arxiv.org/abs/2205.10301.
  2. Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan. Graph clustering using effective resistance. arXiv preprint, 2017. URL: https://arxiv.org/abs/1711.06530.
  3. Konstantinos Ameranis, Lorenzo Orecchia, Kunal Talwar, and Charalampos Tsourakakis. Practical almost-linear-time approximation algorithms for hybrid and overlapping graph clustering. In Proceedings of the 39th International Conference on Machine Learning (ICML), pages 17071-17093, 2022. Google Scholar
  4. Sanjeev Arora, Satish Rao, and Umesh Vazirani. Expander flows, geometric embeddings and graph partitioning. Journal of the ACM (JACM), 56(2):1-37, 2009. Google Scholar
  5. Yi-Jun Chang and Thatchaphol Saranurak. Improved distributed expander decomposition and nearly optimal triangle enumeration. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODS), pages 66-73, 2019. Google Scholar
  6. Yi-Jun Chang and Thatchaphol Saranurak. Deterministic distributed expander decomposition and routing with applications in distributed derandomization. In Proceedings of the 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 377-388, 2020. Google Scholar
  7. Jeff Cheeger. A lower bound for the smallest eigenvalue of the laplacian. Problems in analysis, 625(195-199):110, 1970. Google Scholar
  8. 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. arXiv preprint, 2022. URL: https://arxiv.org/abs/2203.00671.
  9. 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 Proceedings of the 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 18-85, 2020. Google Scholar
  10. Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Saranurak. A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond. In Proceedings of the 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1158-1167, 2020. Google Scholar
  11. Michael B. Cohen, Jonathan 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 Proceedings of the 49th Annual Symposium on Theory of Computing (STOC), pages 410-419, 2017. Google Scholar
  12. Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak, and Zihan Tan. The expander hierarchy and its applications to dynamic graph algorithms. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2212-2228. SIAM, 2021. Google Scholar
  13. Monika Henzinger, Satish Rao, and Di Wang. Local flow partitioning for faster edge connectivity. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1919-1938, 2017. Google Scholar
  14. Yiding Hua, Rasmus Kyng, Maximilian Probst Gutenberg, and Zihang Wu. Maintaining expander decompositions via sparse cuts. arXiv preprint, 2022. URL: https://arxiv.org/abs/2204.02519.
  15. 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 Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete algorithms (SODA), pages 217-226, 2014. Google Scholar
  16. Rohit Khandekar, Satish Rao, and Umesh Vazirani. Graph partitioning using single commodity flows. Journal of the ACM, 56(4):1-15, 2009. Google Scholar
  17. Jason Li, Danupon Nanongkai, Debmalya Panigrahi, and Thatchaphol Saranurak. Near-linear time approximations for cut problems via fair cuts. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 240-275, 2023. Google Scholar
  18. David W. Matula and Farhad Shahrokhi. Sparsest cuts and bottlenecks in graphs. Discrete Applied Mathematics, 27(1-2):113-123, 1990. Google Scholar
  19. Lorenzo Orecchia. Fast approximation algorithms for graph partitioning using spectral and semidefinite-programming techniques. PhD thesis, Berkeley, 2011. Google Scholar
  20. Lorenzo Orecchia, Sushant Sachdeva, and Nisheeth K. Vishnoi. Approximating the exponential, the lanczos method and an Õ (m)-time spectral algorithm for balanced separator. In Proceedings of the 44th Annual Symposium on Theory of Computing (STOC), pages 1141-1160, 2012. Google Scholar
  21. Lorenzo Orecchia, Leonard J. Schulman, Umesh V. Vazirani, and Nisheeth K. Vishnoi. On partitioning graphs via single commodity flows. In Proceedings of the 40th Annual Symposium on Theory of Computing (STOC), pages 461-470, 2008. Google Scholar
  22. Harald Räcke, Chintan Shah, and Hanjo Täubig. Computing cut-based hierarchical decompositions in almost linear time. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 227-238, 2014. Google Scholar
  23. Thatchaphol Saranurak and Di Wang. Expander decomposition and pruning: Faster, stronger, and simpler. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2616-2635, 2019. Google Scholar
  24. Jonah Sherman. Breaking the multicommodity flow barrier for O (√log n)-approximations to sparsest cut. In Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS), pages 363-372. IEEE, 2009. Google Scholar
  25. Jiří Šíma and Satu Elisa Schaeffer. On the NP-completeness of some graph cluster measures. In International Conference on Current Trends in Theory and Practice of Computer Science (SOFTSEM), pages 530-537. Springer, 2006. Google Scholar
  26. Daniel D. Sleator and Robert Endre Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26(3):362-391, 1983. Google Scholar
  27. Daniel A. Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the 36th Annual Symposium on Theory of Computing (FOCS), pages 81-90, 2004. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact