Improved Sublinear Algorithms for Classical and Quantum Graph Coloring
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_ | 1866916605807558656 |
|---|---|
| author | Ferber, Asaf Hardiman, Liam Chen, Xiaonan |
| author_facet | Ferber, Asaf Hardiman, Liam Chen, Xiaonan |
| contents | We present three sublinear randomized algorithms for vertex-coloring of graphs with maximum degree $Δ$. The first is a simple algorithm that extends the idea of Morris and Song to color graphs with maximum degree $Δ$ using $Δ+1$ colors. Combined with the greedy algorithm, it achieves an expected runtime of $O(n^{3/2}\sqrt{\log n})$ in the query model, improving on Assadi, Chen, and Khanna's algorithm by a $\sqrt{\log n}$ factor in expectation. When we allow quantum queries to the graph, we can accelerate the first algorithm using Grover's famous algorithm, resulting in a runtime of $\tilde{O}(n^{4/3})$ quantum queries. Finally, we introduce a quantum algorithm for $(1+ε)Δ$-coloring, achieving $O(ε^{-1}n^{5/4}\log^{3/2}n)$ quantum queries, offering a polynomial improvement over the previous best bound by Morris and Song. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_06024 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved Sublinear Algorithms for Classical and Quantum Graph Coloring Ferber, Asaf Hardiman, Liam Chen, Xiaonan Data Structures and Algorithms We present three sublinear randomized algorithms for vertex-coloring of graphs with maximum degree $Δ$. The first is a simple algorithm that extends the idea of Morris and Song to color graphs with maximum degree $Δ$ using $Δ+1$ colors. Combined with the greedy algorithm, it achieves an expected runtime of $O(n^{3/2}\sqrt{\log n})$ in the query model, improving on Assadi, Chen, and Khanna's algorithm by a $\sqrt{\log n}$ factor in expectation. When we allow quantum queries to the graph, we can accelerate the first algorithm using Grover's famous algorithm, resulting in a runtime of $\tilde{O}(n^{4/3})$ quantum queries. Finally, we introduce a quantum algorithm for $(1+ε)Δ$-coloring, achieving $O(ε^{-1}n^{5/4}\log^{3/2}n)$ quantum queries, offering a polynomial improvement over the previous best bound by Morris and Song. |
| title | Improved Sublinear Algorithms for Classical and Quantum Graph Coloring |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.06024 |