{"ID":2849881,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.23913","arxiv_id":"2510.23913","title":"Expander Decomposition for Non-Uniform Vertex Measures","abstract":"A $(φ,ε)$-expander-decomposition of a graph $G$ (with $n$ vertices and $m$ edges) is a partition of $V$ into clusters $V_1,\\ldots,V_k$ with conductance $Φ(G[V_i]) \\ge φ$, such that there are $O(εm)$ inter-cluster edges. Such a decomposition plays a crucial role in many graph algorithms. [Agassy, Dorman, and Kaplan, ICALP 2023] (ADK) gave a randomized $\\tilde{O}(m)$ time algorithm for computing a $(φ, φ\\log^2 {n})$-expander decomposition. In this paper we generalize this result for a broader notion of expansion. Let $μ\\in \\mathbb{R}_{\\ge 0 }^n$ be a vertex measure. A standard generalization of conductance of a cut $(S,\\overline{S})$ is its $μ$-expansion $Φ^μ_G(S,\\overline{S}) = |E(S,\\overline{S})|/\\min \\{μ(S),μ(\\overline{S})\\}$, where $μ(S) = \\sum_{v\\in S} μ(v)$. We present a randomized $\\tilde{O}(m)$ time algorithm for computing a $(φ, φ\\log^2 {n}\\cdot\\frac{μ(V)}{m})$-expander decomposition with respect to $μ$-expansion. A substantial portion of the exposition is adapted from ADK, and this work serves as a convenient reference for generalized expander decomposition.","short_abstract":"A $(φ,ε)$-expander-decomposition of a graph $G$ (with $n$ vertices and $m$ edges) is a partition of $V$ into clusters $V_1,\\ldots,V_k$ with conductance $Φ(G[V_i]) \\ge φ$, such that there are $O(εm)$ inter-cluster edges. Such a decomposition plays a crucial role in many graph algorithms. [Agassy, Dorman, and Kaplan, ICA...","url_abs":"https://arxiv.org/abs/2510.23913","url_pdf":"https://arxiv.org/pdf/2510.23913v2","authors":"[\"Daniel Agassy\",\"Dani Dorfman\",\"Haim Kaplan\"]","published":"2025-10-27T22:42:18Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}