Faster Deterministic Streaming Vertex Coloring
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909026027044864 |
|---|---|
| author | Chechik, Shiri Chen, Hongyi Zhang, Tianyi |
| author_facet | Chechik, Shiri Chen, Hongyi Zhang, Tianyi |
| contents | Graph coloring is a fundamental problem in computer science. In the semi-streaming model, an input graph $G$ on $n$ vertices and maximum degree $Δ$ is presented as a stream of edges, and the goal is to compute a vertex coloring using a small number of colors while storing only $\tilde{O}(n)$ bits of memory.
Recent work has revealed an exponential separation between randomized and deterministic approaches in this setting: while randomized algorithms can achieve a $(Δ+1)$-coloring in a single pass [Assadi, Chen, and Khanna, 2019], any single-pass deterministic algorithm requires $\exp(Δ^{Ω(1)})$ colors [Assadi, Chen, and Sun, 2022]. Consequently, deterministic algorithms that use few colors must necessarily make multiple passes over the stream. Prior to this work, the best known deterministic trade-offs were: an $O(Δ^2)$-coloring in 2 passes, an $O(Δ)$-coloring in $O(\log Δ)$ passes [Assadi, Chen, and Sun, 2022], and a $(Δ+1)$-coloring in $O(\log Δ\cdot \log\log Δ)$ passes [Assadi, Chakrabarti, Ghosh, and Stoeckl, 2023]. It remained open whether better trade-offs -- particularly with sub-logarithmic pass complexity and linear-in-$Δ$ palette size -- were achievable.
In this paper, we present a new deterministic semi-streaming algorithm that computes an $O(Δ)$-coloring in $O(\sqrt{\log Δ})$ passes. This is the first deterministic streaming algorithm to achieve a coloring with palette size linear-in-$Δ$ using sublogarithmic-in-$Δ$ passes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_07644 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Faster Deterministic Streaming Vertex Coloring Chechik, Shiri Chen, Hongyi Zhang, Tianyi Data Structures and Algorithms Graph coloring is a fundamental problem in computer science. In the semi-streaming model, an input graph $G$ on $n$ vertices and maximum degree $Δ$ is presented as a stream of edges, and the goal is to compute a vertex coloring using a small number of colors while storing only $\tilde{O}(n)$ bits of memory. Recent work has revealed an exponential separation between randomized and deterministic approaches in this setting: while randomized algorithms can achieve a $(Δ+1)$-coloring in a single pass [Assadi, Chen, and Khanna, 2019], any single-pass deterministic algorithm requires $\exp(Δ^{Ω(1)})$ colors [Assadi, Chen, and Sun, 2022]. Consequently, deterministic algorithms that use few colors must necessarily make multiple passes over the stream. Prior to this work, the best known deterministic trade-offs were: an $O(Δ^2)$-coloring in 2 passes, an $O(Δ)$-coloring in $O(\log Δ)$ passes [Assadi, Chen, and Sun, 2022], and a $(Δ+1)$-coloring in $O(\log Δ\cdot \log\log Δ)$ passes [Assadi, Chakrabarti, Ghosh, and Stoeckl, 2023]. It remained open whether better trade-offs -- particularly with sub-logarithmic pass complexity and linear-in-$Δ$ palette size -- were achievable. In this paper, we present a new deterministic semi-streaming algorithm that computes an $O(Δ)$-coloring in $O(\sqrt{\log Δ})$ passes. This is the first deterministic streaming algorithm to achieve a coloring with palette size linear-in-$Δ$ using sublogarithmic-in-$Δ$ passes. |
| title | Faster Deterministic Streaming Vertex Coloring |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2605.07644 |