Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player

A $(\phi,\epsilon)$-Expander-decomposition of a graph $G$ is a partition of $V$ into clusters $V_1,\ldots,V_k$ with conductance $\Phi(G[V_i]) \ge \phi$, such that there are at most $\epsilon \phi m$ inter-cluster edges. We consider the problem of computing such a decomposition for a given $G$ and expansion parameter $\phi$, while minimizing $\epsilon$. Saranurak and Wang [SW19] gave a randomized $O(m \log^4m/\phi)$ algorithm for computing a $(\phi, \log^3 n)$-expander decomposition. As a main building block, [SW19] use an adaptation of the algorithm of R\"{a}cke et al. [RST14] for computing an approximate balanced sparse cut. Both algorithms rely on the cut-matching game of Khandekar et al. [KRV09] Orecchia et al. [OSVV08], using spectral analysis, improved upon [KRV09] by giving a fast algorithm that computes a sparse cut with better approximation guarantee. Using the technique of [OSVV08] for computing expander decompositions or balanced cuts [RST14, SW19], encounters many hurdles since the graph structure constantly changes, making it difficult to perform spectral analysis. In this paper, we manage to exploit the technique of [OSVV08] to compute an expander decomposition, hence improving the result by Saranurak and Wang [SW19]. Specifically, we give a randomized algorithm for computing a $(\phi, \log^2 {n})$-expander decomposition of a graph, in $O(m\log^7 m + \frac{m \log^4m}{\phi})$ time. Our new result is achieved by using a novel combination of a symmetric version of the potential functions of [OSVV08, RST14, SW19] with a new variation of Cheeger's inequality for the notion of near-expansion.