# Distributed (∆+1)-coloring in sublogarithmic rounds

@article{Harris2016DistributedI, title={Distributed (∆+1)-coloring in sublogarithmic rounds}, author={David G. Harris and Johannes Schneider and Hsin-Hao Su}, journal={Proceedings of the forty-eighth annual ACM symposium on Theory of Computing}, year={2016} }

The (∆+1)-coloring problem is a fundamental symmetry breaking problem in distributed computing. We give 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 ∆. This implies that the (∆+1)-coloring problem is easier than the maximal independent set problem and the maximal matching problem, due to their lower bounds by Kuhn, Moscibroda, and Wattenhofer [PODC'04]. Our algorithm… Expand

#### Tables and Topics from this paper

#### 80 Citations

(Δ+1) Coloring in the Congested Clique Model

- Computer Science
- ArXiv
- 2018

Improved algorithms for the (∆ + 1) (vertex) coloring problem in the Congested Clique model of distributed computing and a deterministic algorithm that works in O(log ∆) rounds is presented. Expand

Ultrafast Distributed Coloring of High Degree Graphs

- Computer Science
- ArXiv
- 2021

A new randomized distributed algorithm that can color all n-node graphs of maximum degree ∆ ≥ log n in O(log∗ n) rounds and shows that the randomized complexity of ∆ + 1-list coloring in Congest depends inherently on the deterministic complexity of related coloring problems. Expand

Randomized ( ∆ + 1 )-Coloring in O ( log ∗ ∆ ) Congested Clique Rounds

- 2018

(∆ + 1)-vertex coloring is one of the most fundamental symmetry breaking graph problems, receiving tremendous amount of attention over the last decades. We consider the congested clique model where… Expand

Improved Distributed Delta-Coloring

- Computer Science, Mathematics
- PODC
- 2018

We present a randomized distributed algorithm that computes a Δ- coloring in any non-complete graph with maximum degree Δ ≥ 4 in O(log Δ) +2O( √ log log n) rounds, as well as a randomized algorithm… 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

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

Improved Distributed Algorithms for Coloring Interval Graphs with Application to Multicoloring Trees

- Computer Science
- SIROCCO
- 2017

A distributed (1 + )-approximation algorithm for the minimum vertex coloring problem on interval graphs, which runs in the LOCAL model and operates in O( 1 log∗ n) rounds is given and it is proved that the dependency on 1 is also optimal. 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

Deterministic distributed edge-coloring with fewer colors

- Mathematics, Computer Science
- STOC
- 2018

This work presents a deterministic distributed algorithm, in the LOCAL model, that computes a (1+o(1))Δ-edge-coloring in polylogarithmic-time, so long as the maximum degree Δ=Ω(logn), which are the first deterministic algorithms to go below the natural barrier of 2Δ−1 colors. Expand

The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation

- Computer Science, Mathematics
- PODC
- 2019

New randomized algorithms that improve the complexity of the classic (Δ+1)-coloring problem, and its generalization (� Δ+1-list-coloring, in three well-studied models of distributed, parallel, and centralized computation: Distributed Congested Clique, Centralized Local Computation and Massively Parallel Computation. Expand

#### References

SHOWING 1-10 OF 69 REFERENCES

Distributed (δ+1)-coloring in linear (in δ) time

- Mathematics, Computer Science
- STOC '09
- 2009

A deterministic (Δ + 1)-coloring distributed algorithm with running time O(Δ) + 1/2 log* n is presented, which breaks the heuristic barrier of Szegedy and Vishwanathan, and achieves running time which is linear in the maximum degree Δ. 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

Distributed coloring in Õ (√log n) Bit Rounds

- Computer Science, Mathematics
- 2006

For the cycle in which all edges have the same orientation, it is shown that a simple randomized algorithm can achieve a 3-coloring with only O(√log n) rounds of bit transmissions, with high probability, and the bit complexity of coloring an oriented cycle is Ω( ∼log n), with high likelihood, no matter how many colors are allowed. Expand

Distributed coloring algorithms for triangle-free graphs

- Mathematics, Computer Science
- Inf. Comput.
- 2015

This paper gives new distributed algorithms to find ( Δ / k ) -coloring in graphs of girth 4 (triangle-free graphs), girth 5, and trees, and shows that the chromatic number of triangle-free graph classes can be much smaller. Expand

( Δ + 1 )-COLORING IN LINEAR ( IN Δ ) TIME

- 2009

The distributed (Δ + 1)-coloring problem is one of the most fundamental and wellstudied problems in distributed algorithms. Starting with the work of Cole and Vishkin in 1986, a long line of… Expand

Fast distributed algorithms for Brooks-Vizing colourings

- Mathematics, Computer Science
- SODA '98
- 1998

Very simple, randomized, distributed algorithms for vertex coloring G with Δ/k colors in O(k + log n) communication rounds, where k = O(log Δ), which rely on a powerful generalization of Azuma's martingale inequality that is dubbed the Method of Bounded Variances. Expand

Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic and Faulty Networks

- Computer Science
- PODC
- 2015

The question of how to devise algorithms with the same running time also in the more complicated settings of dynamic and faulty networks is settled by devising deterministic algorithms that require O(Δ3/4 log Δ + log* n) time in the static, dynamic, and faulty settings. Expand

Distributed coloring in O/spl tilde/(/spl radic/(log n)) bit rounds

- Computer Science
- Proceedings 20th IEEE International Parallel & Distributed Processing Symposium
- 2006

This work considers the well-known vertex coloring problem: given a graph G, find a coloring of the vertices so that no two neighbors in G have the same color, and shows that for the n-node cycle the bit complexity of the coloring problem is Omega(log n). Expand

Parallel ((Greek D)D+1)-Coloring of Constant-Degree Graphs

- Mathematics, Computer Science
- Inf. Process. Lett.
- 1987

Abstract This paper presents parallel algorithms for coloring a constant-degree graph with a maximum degree of Δ using Δ + 1 colors and for finding a maximal independent set in a constant-degree… 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