Efficient Algorithms for Partitioning Circulant Graphs with Optimal Spectral Approximation
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909787078262784 |
|---|---|
| author | Gavva, Surya Teja Zhang, Peng |
| author_facet | Gavva, Surya Teja Zhang, Peng |
| contents | The Marcus-Spielman-Srivastava theorem (Annals of Mathematics, 2015) for the Kadison-Singer conjecture implies the following result in spectral graph theory: For any undirected graph $G = (V,E)$ with a maximum edge effective resistance at most $α$, there exists a partition of its edge set $E$ into $E_1 \cup E_2$ such that the two edge-induced subgraphs of $G$ spectrally approximates $(1/2)G$ with a relative error $O(\sqrtα)$. However, the proof of this theorem is non-constructive. It remains an open question whether such a partition can be found in polynomial time, even for special classes of graphs.
In this paper, we explore polynomial-time algorithms for partitioning circulant graphs via partitioning their generators. We develop an efficient algorithm that partitions a circulant graph whose generators form an arithmetic progression, with an error matching that in the Marcus-Spielman-Srivastava theorem and optimal, up to a constant. On the other hand, we prove that if the generators of a circulant graph are ``far" from an arithmetic progression, no partition of the generators can yield two circulant subgraphs with an error matching that in the Marcus-Spielman-Srivastava theorem.
In addition, we extend our algorithm to Cayley graphs whose generators are from a product of multiple arithmetic progressions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_11382 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient Algorithms for Partitioning Circulant Graphs with Optimal Spectral Approximation Gavva, Surya Teja Zhang, Peng Combinatorics Data Structures and Algorithms The Marcus-Spielman-Srivastava theorem (Annals of Mathematics, 2015) for the Kadison-Singer conjecture implies the following result in spectral graph theory: For any undirected graph $G = (V,E)$ with a maximum edge effective resistance at most $α$, there exists a partition of its edge set $E$ into $E_1 \cup E_2$ such that the two edge-induced subgraphs of $G$ spectrally approximates $(1/2)G$ with a relative error $O(\sqrtα)$. However, the proof of this theorem is non-constructive. It remains an open question whether such a partition can be found in polynomial time, even for special classes of graphs. In this paper, we explore polynomial-time algorithms for partitioning circulant graphs via partitioning their generators. We develop an efficient algorithm that partitions a circulant graph whose generators form an arithmetic progression, with an error matching that in the Marcus-Spielman-Srivastava theorem and optimal, up to a constant. On the other hand, we prove that if the generators of a circulant graph are ``far" from an arithmetic progression, no partition of the generators can yield two circulant subgraphs with an error matching that in the Marcus-Spielman-Srivastava theorem. In addition, we extend our algorithm to Cayley graphs whose generators are from a product of multiple arithmetic progressions. |
| title | Efficient Algorithms for Partitioning Circulant Graphs with Optimal Spectral Approximation |
| topic | Combinatorics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2509.11382 |