2026-07-22T06:49:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18061 2024-03-06T11:00:54Z ddc:004 open_access

Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player Agassy, Daniel Dorfman, Dani Kaplan, Haim Exapander Decomposition Cut-Matching Game 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel Agassy and Dani Dorfman and Haim Kaplan 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.9 urn:nbn:de:0030-drops-180619 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.9 eng https://creativecommons.org/licenses/by/4.0/legalcode