Superfast Coloring in CONGEST via Efficient Color Sampling

Magnús M. Halldórsson; Alexandre Nolin

doi:10.1007/978-3-030-79527-6_5

Superfast Coloring in CONGEST via Efficient Color Sampling

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

^*Corresponding author for this work

Department of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Citation (Scopus)

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∗nn, 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 language	English
Title of host publication	Structural Information and Communication Complexity - 28th International Colloquium, SIROCCO 2021, Proceedings
Editors	Tomasz Jurdziński, Stefan Schmid
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	68-83
Number of pages	16
ISBN (Print)	9783030795269
DOIs	https://doi.org/10.1007/978-3-030-79527-6_5
Publication status	Published - 2021
Event	28th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2021 - Virtual, Online Duration: 28 Jun 2021 → 1 Jul 2021

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12810 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	28th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2021
City	Virtual, Online
Period	28/06/21 → 1/07/21

Bibliographical note

Funding Information:
Partially supported by Icelandic Research Fund grant 174484-051.

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

Access to Document

10.1007/978-3-030-79527-6_5

Cite this

Halldórsson, M. M., & Nolin, A. (2021). Superfast Coloring in CONGEST via Efficient Color Sampling. In T. Jurdziński, & S. Schmid (Eds.), Structural Information and Communication Complexity - 28th International Colloquium, SIROCCO 2021, Proceedings (pp. 68-83). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12810 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-79527-6_5

Halldórsson, Magnús M. ; Nolin, Alexandre. / Superfast Coloring in CONGEST via Efficient Color Sampling. Structural Information and Communication Complexity - 28th International Colloquium, SIROCCO 2021, Proceedings. editor / Tomasz Jurdziński ; Stefan Schmid. Springer Science and Business Media Deutschland GmbH, 2021. pp. 68-83 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d256818547f248e8a223f8f119368161,

title = "Superfast Coloring in CONGEST via Efficient Color Sampling",

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∗nn, 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.",

author = "Halld{\'o}rsson, {Magn{\'u}s M.} and Alexandre Nolin",

note = "Funding Information: Partially supported by Icelandic Research Fund grant 174484-051. Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 28th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2021 ; Conference date: 28-06-2021 Through 01-07-2021",

year = "2021",

doi = "10.1007/978-3-030-79527-6_5",

language = "English",

isbn = "9783030795269",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "68--83",

editor = "Tomasz Jurdzi{\'n}ski and Stefan Schmid",

booktitle = "Structural Information and Communication Complexity - 28th International Colloquium, SIROCCO 2021, Proceedings",

address = "Germany",

}

Halldórsson, MM & Nolin, A 2021, Superfast Coloring in CONGEST via Efficient Color Sampling. in T Jurdziński & S Schmid (eds), Structural Information and Communication Complexity - 28th International Colloquium, SIROCCO 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12810 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 68-83, 28th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2021, Virtual, Online, 28/06/21. https://doi.org/10.1007/978-3-030-79527-6_5

Superfast Coloring in CONGEST via Efficient Color Sampling. / Halldórsson, Magnús M.; Nolin, Alexandre.
Structural Information and Communication Complexity - 28th International Colloquium, SIROCCO 2021, Proceedings. ed. / Tomasz Jurdziński; Stefan Schmid. Springer Science and Business Media Deutschland GmbH, 2021. p. 68-83 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12810 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Superfast Coloring in CONGEST via Efficient Color Sampling

AU - Halldórsson, Magnús M.

AU - Nolin, Alexandre

PY - 2021

Y1 - 2021

N2 - 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∗nn, 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.

AB - 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∗nn, 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.

UR - http://www.scopus.com/inward/record.url?scp=85111469282&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-79527-6_5

DO - 10.1007/978-3-030-79527-6_5

M3 - Conference contribution

AN - SCOPUS:85111469282

SN - 9783030795269

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 68

EP - 83

BT - Structural Information and Communication Complexity - 28th International Colloquium, SIROCCO 2021, Proceedings

A2 - Jurdziński, Tomasz

A2 - Schmid, Stefan

PB - Springer Science and Business Media Deutschland GmbH

T2 - 28th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2021

Y2 - 28 June 2021 through 1 July 2021

ER -

Halldórsson MM, Nolin A. Superfast Coloring in CONGEST via Efficient Color Sampling. In Jurdziński T, Schmid S, editors, Structural Information and Communication Complexity - 28th International Colloquium, SIROCCO 2021, Proceedings. Springer Science and Business Media Deutschland GmbH. 2021. p. 68-83. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-79527-6_5