License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2023.22
URN: urn:nbn:de:0030-drops-191484
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19148/
Fuchs, Marc ;
Kuhn, Fabian
List Defective Colorings: Distributed Algorithms and Applications
Abstract
The distributed coloring problem is at the core of the area of distributed graph algorithms and it is a problem that has seen tremendous progress over the last few years. Much of the remarkable recent progress on deterministic distributed coloring algorithms is based on two main tools: a) defective colorings in which every node of a given color can have a limited number of neighbors of the same color and b) list coloring, a natural generalization of the standard coloring problem that naturally appears when colorings are computed in different stages and one has to extend a previously computed partial coloring to a full coloring.
In this paper, we introduce list defective colorings, which can be seen as a generalization of these two coloring variants. Essentially, in a list defective coloring instance, each node v is given a list of colors x_{v,1},… ,x_{v,p} together with a list of defects d_{v,1},… ,d_{v,p} such that if v is colored with color x_{v, i}, it is allowed to have at most d_{v, i} neighbors with color x_{v, i}.
We highlight the important role of list defective colorings by showing that faster list defective coloring algorithms would directly lead to faster deterministic (Δ+1)-coloring algorithms in the LOCAL model. Further, we extend a recent distributed list coloring algorithm by Maus and Tonoyan [DISC '20]. Slightly simplified, we show that if for each node v it holds that ∑_{i=1}^p (d_{v,i}+1)² > deg_G²(v)⋅ polylogΔ then this list defective coloring instance can be solved in a communication-efficient way in only O(logΔ) communication rounds. This leads to the first deterministic (Δ+1)-coloring algorithm in the standard CONGEST model with a time complexity of O(√{Δ}⋅ polylog Δ+log^* n), matching the best time complexity in the LOCAL model up to a polylogΔ factor.
BibTeX - Entry
@InProceedings{fuchs_et_al:LIPIcs.DISC.2023.22,
author = {Fuchs, Marc and Kuhn, Fabian},
title = {{List Defective Colorings: Distributed Algorithms and Applications}},
booktitle = {37th International Symposium on Distributed Computing (DISC 2023)},
pages = {22:1--22:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-301-0},
ISSN = {1868-8969},
year = {2023},
volume = {281},
editor = {Oshman, Rotem},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/19148},
URN = {urn:nbn:de:0030-drops-191484},
doi = {10.4230/LIPIcs.DISC.2023.22},
annote = {Keywords: distributed coloring, list coloring, defective coloring}
}
|
Keywords: |
|
distributed coloring, list coloring, defective coloring |
|
Collection: |
|
37th International Symposium on Distributed Computing (DISC 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
05.10.2023 |
