## 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.