Expander Decomposition and Pruning: Faster, Stronger, and Simpler

by Thatchaphol Saranurak and Di Wang

Oded's comments

Looking for a good reference on the topic of expander decomposition, I found this work, which seems ideal for that purpose.

A weak form of expander decomposition is implicit in the sublinear Bipartite Tester for the Bounded Degree Graph model, but the notion used there is less appealing than the one discussed here, let alone that the former paper only handles bounded-degree graphs.

The ideal result is stated in Observation 1.1 of the current paper. Letting $d(S)$ denote the sum of the degrees of vertices in $V$, and $e(S)$ the number of edges with a single endpoint in $S$, we say that a graph $G=(V,E)$ is a $p$-expander if for every vertex-set $S$ it holds that $e(S) \geq p\cdot\min(d(S),d(V-S))$. Then, for any parameter $p$, every graph $G=(V,E)$ has a vertex partition $(V_1,...,V_k)$ such that the subgraph induced by $V_i$ is a $p$-expander and $\sum_{i\in[k]}d(V_i) = O(p\cdot|E|\log|V|)$.

The main result of the current paper (Theorem 1.2) is an almost-linear-time randomized algorithm that finds an almost ideal partition. Specifically, the running time is $\tildeO(|E|/p)$, whereas $\sum_{i\in[k]}d(V_i) = \tildeO(p\cdot|E|)$.

Expander decomposition found numerous applications in a vaiety of algorithmic settings. It is beneficial whenever it is easier to deal with expander graphs than with general graphs and a solution for any graph can be easily obtained from solutions to isolated subgraphs that conatin almost all the original edges.

The original abstract

See arXiv 1812.08958.


Back to list of Oded's choices.