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 \(\phi\)-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/\phi\). Prior work showed that every \(n\)-node and \(m\)-edge graph admits an (\(h,\, s\))-length \(\phi\)-expander decomposition of size log \(n \cdot sn^{O(1/s)} \cdot \phi m\).