Truly Work-efficient Parallel Deterministic (Δ+1)-coloring and Maximal Independent Set

The problem of computing a (Δ+1)-coloring and a maximal independent set (MIS) in parallel has been a central topic in theoretical computer science for decades. For a graph $G=(V,E)$ with $n=|V|$ vertices and $m=|E|$ edges, a (Δ+1)-coloring assigns colors from $\{1,\dots ,\Delta +1\}$ to vertices such that no two adjacent vertices share the same color, where $\Delta$ is the maximum degree. A maximal independent set is a set of vertices no two of which are adjacent, and to which no other vertex can be added without violating independence. Both problems are fundamental primitives in distributed and parallel computing, with applications in scheduling, resource allocation, and network coordination.

Prior work has established randomized parallel algorithms that achieve $O(n+m)$ work and $O(\mathrm{poly}\log n)$ depth, but deterministic algorithms with the same guarantees have remained elusive. The main challenge is that deterministic symmetry breaking typically requires more work or greater depth. Hutton and Melrod address this gap by providing deterministic parallel algorithms that are truly work-efficient, meaning they perform $O(n+m)$ total work—linear in the input size—while

The main result of the paper is stated as follows: There exist deterministic parallel algorithms that compute a $(\Delta +1)$-coloring and a maximal independent set for a simple graph with $n$ vertices and $m$ edges in $O(n+m)$ work and $O(\mathrm{poly}\log n)$ depth. Specifically, the depth is $O({\log }^{2}n)$ for both problems. This matches the work of the best randomized algorithms and improves upon previous deterministic algorithms which required either $O(m\log n)$ work or $O({\log }^{3}n)$ depth.

The authors provide a detailed analysis of the work and depth. They show that the total number of operations is bounded by $c(n+m)$ for some constant $c$, and the depth is bounded by $c^{\prime }{\log }^{2}n$ for some constant $c^{\prime }$. The algorithms are deterministic, meaning they do not rely on any randomness, which is crucial for applications requiring reproducibility and worst-case guarantees. The results hold for the EREW PRAM model, a standard model for parallel computation. The paper also discusses extensions to the CRCW PRAM and to the distributed setting, where the algorithms can be implemented in the CONGEST model with $O(\log n)$ rounds for MIS and $O({\log }^{2}n)$ rounds for coloring, though with