Expander Decomposition with Almost Optimal Overhead
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908996660625408 |
|---|---|
| author | Bansal, Nikhil Jambulapati, Arun Saranurak, Thatchaphol |
| author_facet | Bansal, Nikhil Jambulapati, Arun Saranurak, Thatchaphol |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_15015 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Expander Decomposition with Almost Optimal Overhead Bansal, Nikhil Jambulapati, Arun Saranurak, Thatchaphol Data Structures and Algorithms 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. |
| title | Expander Decomposition with Almost Optimal Overhead |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.15015 |