Expander Decomposition with Almost Optimal Overhead

Nikhil Bansal, Arun Jambulapati, Thatchaphol Saranurak

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 mos…