2025/10/11 by Greg Bodwin, Bodwin, Greg, Bernhard Haeupler +5
Computer Science · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Computational Geometry and Mesh Generation
paper · pdf · doi:10.48550/arxiv.2510.10227
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 ⋅ s nO(1/s) ⋅ ϕm. In this work, we give a simple proof of the existence of (h, s)-length ϕ-expander decompositions with an improved size of s nO(1/s)⋅ ϕ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⋅ s3 nO(1/s) to s⋅ nO(1/s).