Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $\Delta$-Coloring
TheoretiCS · 2023
DOI: 10.46298/theoretics.23.9 ↗Kurz gefasst
Fachartikel in der Zeitschrift TheoretiCS, 2023. Verfasst von Sepehr Assadi und 2 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref).
Abstract (Originalsprache)
Every graph with maximum degree $\Delta$ can be colored with $(\Delta+1)$ colors using a simple greedy algorithm. Remarkably, recent work has shown that one can find such a coloring even in the semi-streaming model. But, in reality, one almost never needs $(\Delta+1)$ colors to properly color a graph. Indeed, the celebrated \Brooks' theorem states that every (connected) graph beside cliques and odd cycles can be colored with $\Delta$ colors. Can we find a $\Delta$-coloring in the semi-streaming model as well? We settle this key question in the affirmative by designing a randomized semi-streaming algorithm that given any graph, with high probability, either correctly declares that the graph is not $\Delta$-colorable or outputs a $\Delta$-coloring of the graph. The proof of this result starts with a detour. We first (provably) identify the extent to which the previous approaches for streaming coloring fail for $\Delta$-coloring: for instance, all these approaches can handle streams with repeated edges and they can run in $o(n^2)$ time -- we prove that neither of these tasks is possible for $\Delta$-coloring. These impossibility results however pinpoint exactly what is missing from prior approaches when it comes to $\Delta$-coloring. We then build on these insights to design a semi-streaming algorithm that uses $(i)$ a novel sparse-recovery approach based on sparse-dense decompositions to (partially) recover the "problematic" subgraphs of the input -- the ones that form the basis of our impossibility results -- and $(ii)$ a new coloring approach for these subgraphs that allows for recoloring of other vertices in a controlled way without relying on local explorations or finding "augmenting paths" that are generally impossible for semi-streaming algorithms. We believe both these techniques can be of independent interest.
Zitieren
APA
Assadi, S., Kumar, P., & Mittal, P. (2023). Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $\Delta$-Coloring. TheoretiCS. https://doi.org/10.46298/theoretics.23.9
Vancouver
Assadi S, Kumar P, Mittal P. Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $\Delta$-Coloring. TheoretiCS. 2023. doi:10.46298/theoretics.23.9
BibTeX
@article{Assadi2023,
author = {Assadi, Sepehr and Kumar, Pankaj and Mittal, Parth},
title = {Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $\Delta$-Coloring},
journal = {TheoretiCS},
year = {2023},
doi = {10.46298/theoretics.23.9}
}
EUVIMED