- Deterministic O(poly(Δ)) Vertex Coloring in the Streaming Model
- Project Year:
2020
- REU Student (s):
Andrew Chen | Carnegie Mellon University PA
- Project Mentor (s) :
Sepehr Assadi - Computer Science
- Project Abstract:
We studied the problem of deterministic vertex coloring in the semi-streaming model. The (Δ + 1)-coloring problem is easily solved in the classical setting via a greedy coloring, where Δ is the maximum degree. In the streaming model, we are limited to a memory of size O(n) and can only read off edges of the graph one at a time. Although there exist randomized algorithms solving the (Δ + 1)-coloring problem in the semi-streaming model, it is unknown whether there exists a deterministic such algorithm. We establish two deterministic O(poly(Δ))-coloring algorithms towards this; the first produces an O(Δ3)- coloring in two passes, while the second produces an O(Δ2)-coloring in O(log Δ) passes. We also briefly touch upon the related independent set problem, and prove a deterministic Ω(n/Δ2)-independent set single-pass algorithm.
