# Simple, deterministic, constant-round coloring in the congested clique

Czumaj A, Davies P, Parter M. 2020. Simple, deterministic, constant-round coloring in the congested clique. Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 309–318.

Download

ColoringArxiv.pdf
520.05 KB

*Conference Paper*|

*Published*|

*English*

Author

Department

Abstract

We settle the complexity of the (Δ+1)-coloring and (Δ+1)-list coloring problems in the CONGESTED CLIQUE model by presenting a simple deterministic algorithm for both problems running in a constant number of rounds. This matches the complexity of the recent breakthrough randomized constant-round (Δ+1)-list coloring algorithm due to Chang et al. (PODC'19), and significantly improves upon the state-of-the-art O(logΔ)-round deterministic (Δ+1)-coloring bound of Parter (ICALP'18).
A remarkable property of our algorithm is its simplicity. Whereas the state-of-the-art randomized algorithms for this problem are based on the quite involved local coloring algorithm of Chang et al. (STOC'18), our algorithm can be described in just a few lines. At a high level, it applies a careful derandomization of a recursive procedure which partitions the nodes and their respective palettes into separate bins. We show that after O(1) recursion steps, the remaining uncolored subgraph within each bin has linear size, and thus can be solved locally by collecting it to a single node. This algorithm can also be implemented in the Massively Parallel Computation (MPC) model provided that each machine has linear (in n, the number of nodes in the input graph) space.
We also show an extension of our algorithm to the MPC regime in which machines have sublinear space: we present the first deterministic (Δ+1)-list coloring algorithm designed for sublinear-space MPC, which runs in O(logΔ+loglogn) rounds.

Publishing Year

Date Published

2020-07-01

Proceedings Title

Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing

Page

309-318

Conference

PODC: Symposium on Principles of Distributed Computing

Conference Location

Salerno, Italy

Conference Date

2020-08-03 – 2020-08-07

IST-REx-ID

### Cite this

Czumaj A, Davies P, Parter M. Simple, deterministic, constant-round coloring in the congested clique. In:

*Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing*. Association for Computing Machinery; 2020:309-318. doi:10.1145/3382734.3405751Czumaj, A., Davies, P., & Parter, M. (2020). Simple, deterministic, constant-round coloring in the congested clique. In

*Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing*(pp. 309–318). Salerno, Italy: Association for Computing Machinery. https://doi.org/10.1145/3382734.3405751Czumaj, Artur, Peter Davies, and Merav Parter. “Simple, Deterministic, Constant-Round Coloring in the Congested Clique.” In

*Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing*, 309–18. Association for Computing Machinery, 2020. https://doi.org/10.1145/3382734.3405751.A. Czumaj, P. Davies, and M. Parter, “Simple, deterministic, constant-round coloring in the congested clique,” in

*Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing*, Salerno, Italy, 2020, pp. 309–318.Czumaj, Artur, et al. “Simple, Deterministic, Constant-Round Coloring in the Congested Clique.”

*Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing*, Association for Computing Machinery, 2020, pp. 309–18, doi:10.1145/3382734.3405751.**All files available under the following license(s):**

**Copyright Statement:**

**This Item is protected by copyright and/or related rights.**[...]

**Main File(s)**

File Name

ColoringArxiv.pdf
520.05 KB

Access Level

Open Access

Date Uploaded

2020-10-08

MD5 Checksum

46fe4fc58a64eb04068115573f631d4c

### Export

Marked PublicationsOpen Data ISTA Research Explorer

### Sources

arXiv 2009.06043