Abstract
We prove new bounds on the distributed fractional coloring problem in the LOCAL model. A fractional ccoloring of a graph G = (V,E) is a fractional covering of the nodes of G with independent sets such that each independent set I of G is assigned a fractional value λ_I ∈ [0,1]. The total value of all independent sets of G is at most c, and for each node v ∈ V, the total value of all independent sets containing v is at least 1. Equivalently, fractional ccolorings can also be understood as multicolorings as follows. For some natural numbers p and q such that p/q ≤ c, each node v is assigned a set of at least q colors from {1,…,p} such that adjacent nodes are assigned disjoint sets of colors. The minimum c for which a fractional ccoloring of a graph G exists is called the fractional chromatic number χ_f(G) of G.
Recently, [Bousquet, Esperet, and Pirot; SIROCCO '21] showed that for any constant ε > 0, a fractional (Δ+ε)coloring can be computed in Δ^{O(Δ)} + O(Δ⋅log^* n) rounds. We show that such a coloring can be computed in only O(log² Δ) rounds, without any dependency on n.
We further show that in O((log n)/ε) rounds, it is possible to compute a fractional (1+ε)χ_f(G)coloring, even if the fractional chromatic number χ_f(G) is not known. That is, the fractional coloring problem can be approximated arbitrarily well by an efficient algorithm in the LOCAL model. For the standard coloring problem, it is only known that an O((log n)/(log log n))approximation can be computed in polylogarithmic time in the LOCAL model. We also show that our distributed fractional coloring approximation algorithm is best possible. We show that in trees, which have fractional chromatic number 2, computing a fractional (2+ε)coloring requires at least Ω((log n)/ε) rounds.
We finally study fractional colorings of regular grids. In [Bousquet, Esperet, and Pirot; SIROCCO '21], it is shown that in regular grids of bounded dimension, a fractional (2+ε)coloring can be computed in time O(log^* n). We show that such a coloring can even be computed in O(1) rounds in the LOCAL model.
BibTeX  Entry
@InProceedings{balliu_et_al:LIPIcs.OPODIS.2021.18,
author = {Balliu, Alkida and Kuhn, Fabian and Olivetti, Dennis},
title = {{Improved Distributed Fractional Coloring Algorithms}},
booktitle = {25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
pages = {18:118:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772198},
ISSN = {18688969},
year = {2022},
volume = {217},
editor = {Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15793},
URN = {urn:nbn:de:0030drops157935},
doi = {10.4230/LIPIcs.OPODIS.2021.18},
annote = {Keywords: distributed graph algorithms, distributed coloring, locality, fractional coloring}
}
Keywords: 

distributed graph algorithms, distributed coloring, locality, fractional coloring 
Collection: 

25th International Conference on Principles of Distributed Systems (OPODIS 2021) 
Issue Date: 

2022 
Date of publication: 

28.02.2022 