Superfast coloring in CONGEST via efficient color sampling

Magnús M. Halldórsson, Alexandre Nolin*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

We present a procedure for efficiently sampling colors in the CONGEST model. It allows nodes whose number of colors exceeds their number of neighbors by a constant fraction to sample up to Θ(log⁡n) semi-random colors unused by their neighbors in O(1) rounds, even in the distance-2 setting. This yields algorithms with O(log⁡Δ) complexity for different edge-coloring, vertex coloring, and distance-2 coloring problems, matching the best possible. In particular, we obtain an O(log⁡Δ)-round CONGEST algorithm for (1+ϵ)Δ-edge coloring when Δ=Ω(log1+1/log⁡n⁡n), and a poly(log⁡log⁡n)-round algorithm for (2Δ−1)-edge coloring in general. The sampling procedure is inspired by a seminal result of Newman in communication complexity.

Original languageEnglish
Article number113711
JournalTheoretical Computer Science
Volume948
DOIs
Publication statusPublished - 28 Feb 2023

Bibliographical note

Funding Information:
Partially supported by Icelandic Research Fund grants 174484 and 217965.The authors declare the following financial interests/personal relationships which may be considered as potential competing interests: Icelandic Research Fund grants 174484 and 217965.

Publisher Copyright:
© 2023 Elsevier B.V.

Other keywords

  • Congest model
  • Distributed coloring
  • Edge coloring
  • Pseudorandomness

Fingerprint

Dive into the research topics of 'Superfast coloring in CONGEST via efficient color sampling'. Together they form a unique fingerprint.

Cite this