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

Daniel Agassy, Dani Dorfman, Haim Kaplan

A $(\ddot{I}•,\hat{I}\mu )$-expander-decomposition of a graph $G$ (with $n$ vertices and $m$ edges) is a partition of $V$ into clusters $V_1,\dots ,V_k$ with conductance $\hat{I}¦(G[V_i])\ge \ddot{I}•$, such…