Simple Length-Constrained Expander Decompositions

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 · sn^O(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 sn^O(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.