Sparsest Cut and Eigenvalue Multiplicities on Low Degree Abelian Cayley Graphs

Version History: Preliminary version posted as arXiv:2412.17115 [cs.DS]

Abstract: Whether or not the Sparsest Cut problem admits an efficient O(1)-approximation algorithm is a fundamental algorithmic question with connections to geometry and the Unique Games Conjecture. 

Revisiting spectral algorithms for Sparsest Cut, we present a novel, simple algorithm that combines eigenspace enumeration with a new algorithm for the Cut Improvement problem. The runtime of our algorithm is parametrized by a quantity that we call the solution dimension SDε(G): the smallest k such that the subspace spanned by the first k Laplacian eigenvectors contains all but ε fraction of a sparsest cut. 

Our algorithm matches the guarantees of prior methods based on the threshold-rank paradigm, while also extending beyond them. To illustrate this, we study its performance on low degree Cayley graphs over Abelian groups– canonical examples of graphs with poor expansion properties. 

We prove that low degree Abelian Cayley graphs have small solution dimension, yielding an algorithm that computes a (1 + ε)-approximation to the uniform Sparsest Cut of a degree-d Cayley graph over an Abelian group of size n in time nO(1) ·exp{(d/ε)O(d)}. Along the way to bounding the solution dimension of Abelian Cayley graphs, we analyze their sparse cuts and spectra, proving that the collection of O(1)-approximate sparsest cuts has an ε-net of size exp{(d/ε)O(d)} and that the multiplicity of λ2 is bounded by 2O(d). The latter bound is tight and improves on a previous bound of 2O(d2) by Lee and Makarychev.