Expander Decomposition with Almost Optimal Overhead
2026/02/16 by Nikhil Bansal, Arun Jambulapati, Thatchaphol Saranurak · 1 voice
Computer Science · #cs.DS
paper · pdf · doi:10.48550/arxiv.2602.15015
arxiv published 2026/02/16 · arxiv updated 2026/04/28
Abstract
We present the first polynomial-time algorithm for computing a near-optimal flow-expander decomposition. Given a graph G and a parameter φ, our algorithm removes at most a φlog1+o(1)n fraction of edges so that every remaining connected component is a φ-flow-expander (a stronger guarantee than being a φ-cut-expander). This achieves overhead log1+o(1)n, nearly matching the Ω(log n) graph-theoretic lower bound that already holds for cut-expander decompositions, up to a logo(1)n factor. Prior polynomial-time algorithms required removing O(φlog1.5n) and O(φlog2n) fractions of edges to guarantee φ-cut-expander and φ-flow-expander components, respectively.
Citations
- An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time
- Improved Directed Expander Decompositions
- Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
- Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
- On the Streaming Complexity of Expander Decomposition
- Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time
- On Approximating Cutwidth and Pathwidth
- Fully Dynamic Exact Edge Connectivity in Sublinear Time
- Expander Decomposition in Dynamic Streams
- On Weighted Graph Sparsification by Linear Sketching
- Near-Optimal Deterministic Vertex-Failure Connectivity Oracles
- Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
- Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing
- Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization
- The Expander Hierarchy and its Applications to Dynamic Graph Algorithms
- A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond
- Expander Decomposition and Pruning: Faster, Stronger, and Simpler
- Almost Polynomial Hardness of Node-Disjoint Paths in Grids
- Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time
- Polynomial Bounds for the Grid-Minor Theorem
- An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
- An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
- A Polylogarithimic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
- On Vertex Sparsifiers with Steiner Nodes
- Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Graph Clustering using Effective Resistance
Discussions
Related