EUVIMEDEUVIMED entdecken
Crossref

Locally-iterative Distributed (Δ + 1)-coloring and Applications

Leonid Barenboim, Michael Elkin, Uri Goldenberg

Journal of the ACM · 28.02.2022 · 69 (1) · 1-26

DOI: 10.1145/3486625 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of the ACM, online erschienen am 07.12.2021. Verfasst von Leonid Barenboim und 2 weiteren Autor:innen. Die Arbeit wurde bisher 16-mal zitiert (Crossref) und nennt 45 Literaturangaben. Gefördert von: Israel Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We consider graph coloring and related problems in the distributed message-passing model. Locally-iterative algorithms are especially important in this setting. These are algorithms in which each vertex decides about its next color only as a function of the current colors in its 1-hop-neighborhood . In STOC’93 Szegedy and Vishwanathan showed that any locally-iterative Δ + 1-coloring algorithm requires Ω (Δ log Δ + log * n ) rounds, unless there exists “a very special type of coloring that can be very efficiently reduced” [ 44 ]. No such special coloring has been found since then. This led researchers to believe that Szegedy-Vishwanathan barrier is an inherent limitation for locally-iterative algorithms and to explore other approaches to the coloring problem [ 2 , 3 , 19 , 32 ]. The latter gave rise to faster algorithms, but their heavy machinery that is of non-locally-iterative nature made them far less suitable to various settings. In this article, we obtain the aforementioned special type of coloring. Specifically, we devise a locally-iterative Δ + 1-coloring algorithm with running time O (Δ + log * n ), i.e., below Szegedy-Vishwanathan barrier. This demonstrates that this barrier is not an inherent limitation for locally-iterative algorithms. As a result, we also achieve significant improvements for dynamic, self-stabilizing, and bandwidth-restricted settings. This includes the following results: We obtain self-stabilizing distributed algorithms for Δ + 1-vertex-coloring, (2Δ - 1)-edge-coloring, maximal independent set, and maximal matching with O (Δ + log * n ) time. This significantly improves previously known results that have O(n) or larger running times [ 23 ]. We devise a (2Δ - 1)-edge-coloring algorithm in the CONGEST model with O (Δ + log * n ) time and O (Δ)-edge-coloring in the Bit-Round model with O (Δ + log n ) time. The factors of log * n and log n are unavoidable in the CONGEST and Bit-Round models, respectively. Previously known algorithms had superlinear dependency on Δ for (2Δ - 1)-edge-coloring in these models. We obtain an arbdefective coloring algorithm with running time O (√ Δ + log * n ). Such a coloring is not necessarily proper, but has certain helpful properties. We employ it to compute a proper (1 + ε)Δ-coloring within O (√ Δ + log * n ) time and Δ + 1-coloring within O (√ Δ log Δ log * Δ + log * n ) time. This improves the recent state-of-the-art bounds of Barenboim from PODC’15 [ 2 ] and Fraigniaud et al. from FOCS’16 [ 19 ] by polylogarithmic factors. Our algorithms are applicable to the SET-LOCAL model [ 25 ] (also known as the weak LOCAL model). In this model a relatively strong lower bound of Ω (Δ 1/3 ) is known for Δ + 1-coloring. However, most of the coloring algorithms do not work in this model. (In Reference [ 25 ] only Linial’s O (Δ 2 )-time algorithm and Kuhn-Wattenhofer O (Δ log Δ)-time algorithms are shown to work in it.) We obtain the first linear-in-Δ Δ + 1-coloring algorithms that work also in this model.

Förderung

  • Israel Science Foundation

Zitieren

APA

Barenboim, L., Elkin, M., & Goldenberg, U. (2022). Locally-iterative Distributed (Δ + 1)-coloring and Applications. Journal of the ACM, 69(1), 1-26. https://doi.org/10.1145/3486625

Vancouver

Barenboim L, Elkin M, Goldenberg U. Locally-iterative Distributed (Δ + 1)-coloring and Applications. Journal of the ACM. 2022;69(1):1-26. doi:10.1145/3486625

BibTeX
@article{Barenboim2022,
  author = {Barenboim, Leonid and Elkin, Michael and Goldenberg, Uri},
  title = {Locally-iterative Distributed (Δ + 1)-coloring and Applications},
  journal = {Journal of the ACM},
  year = {2022},
  volume = {69},
  number = {1},
  pages = {1--26},
  doi = {10.1145/3486625}
}
Kostenlos starten →