Expander Decomposition with Almost Optimal Overhead
2026-02-16 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors introduce a new algorithm that breaks a graph into parts where each part is well-connected in terms of flow, which is a stronger condition than just being well-connected by cuts. Their method removes fewer edges than previous algorithms while still achieving nearly the best possible guarantee on connectivity. This improves on older methods by reducing the number of edges that need to be deleted and works in polynomial time. The result is close to the theoretical limit for such decompositions.
graphflow-expandercut-expanderexpander decompositionpolynomial-time algorithmgraph connectivityedge removalalgorithmic graph theory
Authors
Nikhil Bansal, Arun Jambulapati, Thatchaphol Saranurak
Abstract
We present the first polynomial-time algorithm for computing a near-optimal \emph{flow}-expander decomposition. Given a graph $G$ and a parameter $φ$, our algorithm removes at most a $φ\log^{1+o(1)}n$ fraction of edges so that every remaining connected component is a $φ$-\emph{flow}-expander (a stronger guarantee than being a $φ$-\emph{cut}-expander). This achieves overhead $\log^{1+o(1)}n$, nearly matching the $Ω(\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(φ\log^{1.5}n)$ and $O(φ\log^{2}n)$ fractions of edges to guarantee $φ$-cut-expander and $φ$-flow-expander components, respectively.