Expander Decomposition with Almost Optimal Overhead

Abstract

We present the first polynomial-time algorithm for computing a near-optimal \emph{flow}-expander decomposition. Given a graph $G$ and a parameter $\ddot{I}•$, our algorithm removes at most a $\ddot{I}•{\log }^{1+o(1)}n$ fraction of edges so that every remaining connected component is a $\ddot{I}•$-\emph{flow}-expander (a stronger guarantee than being a $\ddot{I}•$-\emph{cut}-expander). This achieves overhead ${\log }^{1+o(1)}n$, nearly matching the $\hat{I}\text{c◯}(\log n)$ graph-theoretic lower bound that already holds for cut-expander decompositions, up to a ${\log }^{o(1)}n$ factor. Prior polynomial-time algorithms required removing $O(\ddot{I}•{\log }^{1.5}n)$ and $O(\ddot{I}•{\log }^{2}n)$ fractions of edges to guarantee $\ddot{I}•$-cut-expander and $\ddot{I}•$-flow-expander components, respectively.