{"ID":2857129,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.10227","arxiv_id":"2510.10227","title":"Simple Length-Constrained Expander Decompositions","abstract":"Length-constrained expander decompositions are a new graph decomposition that has led to several recent breakthroughs in fast graph algorithms. Roughly, an $(h, s)$-length $φ$-expander decomposition is a small collection of length increases to a graph so that nodes within distance $h$ can route flow over paths of length $hs$ while using each edge to an extent at most $1/φ$. Prior work showed that every $n$-node and $m$-edge graph admits an $(h, s)$-length $φ$-expander decomposition of size $\\log n \\cdot s n^{O(1/s)} \\cdot φm$. In this work, we give a simple proof of the existence of $(h, s)$-length $φ$-expander decompositions with an improved size of $s n^{O(1/s)}\\cdot φm$. Our proof is a straightforward application of the fact that the union of sparse length-constrained cuts is itself a sparse length-constrained cut. In deriving our result, we improve the loss in sparsity when taking the union of sparse length-constrained cuts from $\\log ^3 n\\cdot s^3 n^{O(1/s)}$ to $s\\cdot n^{O(1/s)}$.","short_abstract":"Length-constrained expander decompositions are a new graph decomposition that has led to several recent breakthroughs in fast graph algorithms. Roughly, an $(h, s)$-length $φ$-expander decomposition is a small collection of length increases to a graph so that nodes within distance $h$ can route flow over paths of lengt...","url_abs":"https://arxiv.org/abs/2510.10227","url_pdf":"https://arxiv.org/pdf/2510.10227v1","authors":"[\"Greg Bodwin\",\"Bernhard Haeupler\",\"D Ellis Hershkowitz\",\"Zihan Tan\"]","published":"2025-10-11T14:04:15Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}