2026-08-17T03:36:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24382 2025-12-12T15:01:17Z ddc:004 open_access

Sparsest Cut and Eigenvalue Multiplicities on Low Degree Abelian Cayley Graphs d'Orsi, Tommaso Jones, Chris Ruotolo, Jake Vadhan, Salil Zhang, Jiyu Sparsest Cut Spectral Graph Theory Cayley Graphs Approximation Algorithms 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 n^O(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 λ₂ is bounded by 2^O(d). The latter bound is tight and improves on a previous bound of 2^O(d²) by Lee and Makarychev. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tommaso d'Orsi and Chris Jones and Jake Ruotolo and Salil Vadhan and Jiyu Zhang 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.16 urn:nbn:de:0030-drops-243827 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.16 eng https://creativecommons.org/licenses/by/4.0/legalcode