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 $\ddot{I}•$-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/\ddot{I}•$. Prior work showed that every $n$-node and $m$-edge graph admits an $(h,s)$-length $\ddot{I}•$-expander decomposition of size $\log n\cdot s{n}^{O(1/s)}\cdot \ddot{I}•m$. In this work, we give a simple proof of the existence of $(h,s)$-length $\ddot{I}•$-expander decompositions with an improved size of $s{n}^{O(1/s)}\cdot \ddot{I}•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)}$.

@SOSA 2026