Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player
share
A (ϕ,ϵ)-Expander-decomposition of a graph G is a partition of V into clusters V_1,…,V_k with conductance Φ(G[V_i]) ≥ϕ, such that there are at most ϵϕ m inter-cluster edges. We consider the problem of computing such a decomposition for a given G and expansion parameter ϕ, while minimizing ϵ. Saranurak and Wang [SW19] gave a randomized O(m log^4m/ϕ) algorithm for computing a (ϕ, log^3 n)-expander decomposition. As a main building block, [SW19] use an adaptation of the algorithm of Rä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 (ϕ, log^2 n)-expander decomposition of a graph, in O(mlog^7 m + m log^4m/ϕ) 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.
READ FULL TEXT