Sparsest cut and eigenvalue multiplicities on low degree Abelian Cayley graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909815703339008 |
|---|---|
| author | d'Orsi, Tommaso Jones, Chris Ruotolo, Jake Vadhan, Salil Zhang, Jiyu |
| author_facet | d'Orsi, Tommaso Jones, Chris Ruotolo, Jake Vadhan, Salil Zhang, Jiyu |
| contents | 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 $\text{SD}_\varepsilon(G)$: the smallest $k$ such that the subspace spanned by the first $k$ Laplacian eigenvectors contains all but $\varepsilon$ 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+\varepsilon)$-approximation to the uniform Sparsest Cut of a degree-$d$ Cayley graph over an Abelian group of size $n$ in time $n^{O(1)}\cdot\exp(d/\varepsilon)^{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 $\varepsilon$-net of size $\exp(d/\varepsilon)^{O(d)}$ and that the multiplicity of $λ_2$ is bounded by $2^{O(d)}$. The latter bound is tight and improves on a previous bound of $2^{O(d^2)}$ by Lee and Makarychev. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_17115 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Sparsest cut and eigenvalue multiplicities on low degree Abelian Cayley graphs d'Orsi, Tommaso Jones, Chris Ruotolo, Jake Vadhan, Salil Zhang, Jiyu Data Structures and Algorithms Discrete Mathematics Combinatorics 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 $\text{SD}_\varepsilon(G)$: the smallest $k$ such that the subspace spanned by the first $k$ Laplacian eigenvectors contains all but $\varepsilon$ 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+\varepsilon)$-approximation to the uniform Sparsest Cut of a degree-$d$ Cayley graph over an Abelian group of size $n$ in time $n^{O(1)}\cdot\exp(d/\varepsilon)^{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 $\varepsilon$-net of size $\exp(d/\varepsilon)^{O(d)}$ and that the multiplicity of $λ_2$ is bounded by $2^{O(d)}$. The latter bound is tight and improves on a previous bound of $2^{O(d^2)}$ by Lee and Makarychev. |
| title | Sparsest cut and eigenvalue multiplicities on low degree Abelian Cayley graphs |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2412.17115 |