Sparsifying Cayley Graphs on Every Group
Abstract
A classic result in graph theory, due to Batson, Spielman, and Srivastava (STOC 2009) shows that every graph admits a \((1 \pm \varepsilon)\) cut (or spectral) sparsifier which preserves only \(O(n/\varepsilon^2)\) reweighted edges. However, when applying this result to Cayley graphs, the resulting sparsifier is no longer necessarily a Cayley graph — it can be an arbitrary subset of edges.
Fields of Study & Subjects
Advanced Graph Theory Research
Complexity and Algorithms in Graphs
Graph Labeling and Dimension Problems
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 6029–6041
- Publication date
- 1 January 2026
- Language
- EN