# Ultrafast Distributed Coloring of High Degree Graphs

@article{Halldorsson2021UltrafastDC, title={Ultrafast Distributed Coloring of High Degree Graphs}, author={Magn'us M. Halld'orsson and Alexandre Nolin and Tigran Tonoyan}, journal={ArXiv}, year={2021}, volume={abs/2105.04700} }

We give a new randomized distributed algorithm for the ∆ + 1-list coloring problem. The algorithm and its analysis dramatically simplify the previous best result known of Chang, Li, and Pettie [SICOMP 2020]. This allows for numerous refinements, and in particular, we can color all n-node graphs of maximum degree ∆ ≥ log n in O(log∗ n) rounds. The algorithm works in the Congest model, i.e., it uses only O(log n) bits per message for communication. On low-degree graphs, the algorithm shatters the… Expand

#### Figures from this paper

#### One Citation

Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition

- Computer Science, Mathematics
- ArXiv
- 2020

We present a simple deterministic distributed algorithm that computes a $(\Delta+1)$-vertex coloring in $O(\log^2 \Delta \cdot \log n)$ rounds, in any graph with at most $n$ nodes and maximum degree… Expand

#### References

SHOWING 1-10 OF 36 REFERENCES

Superfast Coloring in CONGEST via Efficient Color Sampling

- Computer Science
- SIROCCO
- 2021

An O(log∗ ∆)-round CONGEST algorithm for (2∆− 1)-edge coloring when ∆ ≥ log n, and poly(log logn)-round algorithm in general is obtained. Expand

Distributed (∆+1)-coloring in sublogarithmic rounds

- Computer Science, Mathematics
- STOC
- 2016

A new randomized coloring algorithm for (∆+1)-coloring running in O(√log ∆)+ 2^O( ∼log log n) rounds with probability 1-1/n^Ω(1) in a graph with n nodes and maximum degree ∆. Expand

An optimal distributed (Δ+1)-coloring algorithm?

- Mathematics, Computer Science
- STOC
- 2018

This paper presents a new algorithm for (Δ+1)-list coloring in the randomized LOCAL model running in O(log∗n + Detd(poly logn)) time, where Det d(n′) is the deterministic complexity of (deg+1-list coloring) on n′-vertex graphs. Expand

On the complexity of distributed graph coloring

- Mathematics, Computer Science
- PODC '06
- 2006

This paper proves new strong lower bounds for two special kinds of coloring algorithms, and proves a time lower bound of Ω(Δ/log<sup>2</sup> Δ+ log*<i>m</i>) to obtain an <i>O</i>(Δ)-coloring. Expand

Improved distributed algorithms for coloring and network decomposition problems

- Mathematics, Computer Science
- STOC '92
- 1992

It is shown that A-coloring G is reducible in 0(log3 n/log A) time to (A+ I)-vertex coloring G in a distributed model, which leads to fast distributed algorithms, and a linear–processor NC algorithm, for Acoloring. Expand

Sublinear Algorithms for (Δ+ 1) Vertex Coloring

- Computer Science
- SODA
- 2019

A remarkably simple meta-algorithm for the (∆ + 1) coloring problem: Sample O(log n) colors for each vertex independently and uniformly at random from the ∆+ 1 colors; find a proper coloring of the graph using only the sampled colors of each vertex. Expand

(2Δ - l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting

- Computer Science, Mathematics
- SODA
- 2015

It is shown that a (2Δ − 1)-edge-coloring can be computed in time smaller than loge n for any e > 0, specifically, in eO([EQUATION]log log n) rounds. Expand

Local Conflict Coloring

- Computer Science, Mathematics
- 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)
- 2016

This work introduces conflict coloring as a general symmetry-breaking task that includes all the aforementioned tasks as specific instantiations - conflict coloring includes all locally checkable labeling tasks from [Naor & Stockmeyer, STOC 1993] and yields an LCA which requires a smaller number of probes than the previously best known algorithm for vertex-coloring. Expand

Network decomposition and locality in distributed computation

- Computer Science
- 30th Annual Symposium on Foundations of Computer Science
- 1989

The authors introduce a concept of network decomposition, a partitioning of an arbitrary graph into small-diameter connected components, such that the graph created by contracting each component into… Expand

Distributive graph algorithms Global solutions from local data

- Mathematics, Computer Science
- 28th Annual Symposium on Foundations of Computer Science (sfcs 1987)
- 1987

A maximal independent set in an n-cycle cannot be found faster than Ω(log* n) and this is optimal by [CV]; the d-regular tree of radius r cannot be colored with fewer than √d colors in time 2r / 3. Expand