Papers › Expander Decomposition and Pruning: Faster, Stronger, and Simpler
Expander Decomposition and Pruning: Faster, Stronger, and Simpler
Thatchaphol Saranurak, Di Wang
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We study the problem of graph clustering where the goal is to partition a graph into clusters, i.e. disjoint subsets of vertices, such that each cluster is well connected internally while sparsely connected to the rest of the graph. In particular, we use a natural bicriteria notion motivated by Kannan, Vempala, and Vetta which we refer to as {\em expander decomposition}. Expander decomposition has become one of the building blocks in the design of fast graph algorithms, most notably in the nearly linear time Laplacian solver by Spielman and Teng, and it also has wide applications in practice. We design algorithm for the parametrized version of expander decomposition, where given a graph G of m edges and a parameter ϕ, our algorithm finds a partition of the vertices into clusters such that each cluster induces a subgraph of conductance at least ϕ (i.e. a ϕ expander), and only a O(ϕ) fraction of the edges in G have endpoints across different clusters. Our algorithm runs in O(m/ϕ) time, and is the first nearly linear time algorithm when ϕ is at least 1/logᴼ⁽¹⁾ m, which is the case in most practical settings and theoretical applications. Previous results either take Ω(m¹⁺ᵒ⁽¹⁾) time, or attain nearly linear time but with a weaker expansion guarantee where each output cluster is guaranteed to be contained inside some unknown ϕ expander. Our result achieve both nearly linear running time and the strong expander guarantee for clusters. Moreover, a main technique we develop for our result can be applied to obtain a much better \emph{expander pruning} algorithm, which is the key tool for maintaining an expander decomposition on dynamic graphs. Finally, we note that our algorithm is developed from first principles based on relatively simple and basic techniques, thus making it very likely to be practical.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections