research-article

Public Access

Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma

Authors:

Jara UittoAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 16, Issue 1

Article No.: 8, Pages 1 - 51

https://doi.org/10.1145/3365004

Published: 15 November 2019 Publication History

All formats PDF

Abstract

The complexity of distributed edge coloring depends heavily on the palette size as a function of the maximum degree Δ. In this article, we explore the complexity of edge coloring in the LOCAL model in different palette size regimes. Our results are as follows.

Lower Bounds: First, we simplify the round elimination technique of Brandt et al. [16] and prove that (2Δ −2)-edge coloring requires Ω (log_Δ log n) time with high probability and Ω (log_Δ n) time deterministically, even on trees. Second, we show that a natural approach to computing (Δ +1)-edge colorings (Vizing’s theorem), namely, extending an arbitrary partial coloring by iteratively recoloring subgraphs, requires Ω (Δ log n) time.

Upper Bounds on General Graphs: We give a randomized edge coloring algorithm that can use palette sizes as small as Δ + Õ(√Δ), which is a natural barrier for randomized approaches. The running time of our (1+ϵ)Δ-edge coloring algorithm is usually dominated by O(\log ϵ⁻¹) calls to a distributed Lovász local lemma (LLL) algorithm. For example, using the Chung-Pettie-Su LLL algorithm, we compute a (1+ϵ)Δ-edge coloring in O(log n) time when ϵ ≥ (log³ Δ) / √ Δ, or O(log_Δ n) + (log log n)^{3 + o(1)} time when ϵ = Ω (1). When Δ is sublogarithmic in n the performance is improved with the Ghaffari-Harris-Kuhn LLL algorithm.

Upper Bounds on Trees: We show that the Ω (log_Δ log n) lower bound can be nearly matched on trees. To establish this result, we develop a new distributed Lovász local lemma algorithm for tree-structured dependency graphs, which arise naturally from O(1)-round probabilistic algorithms run on trees. Specifically, our (1+ϵ)Δ-edge coloring algorithm for trees takes O(log (1 / ϵ)) ⋅ max { log log n\ log log log n, log_{log Δ} log n} time when ϵ ≥ (log³ Δ) / √ Δ, or O(max { log log n\ log log log n, log_Δ log n}) time when ϵ = Ω (1).

References

[1]

N. Alon, L. Babai, and A. Itai. 1986. A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algor. 7, 4 (1986), 567--583.

Abstract

References

Cited By

Index Terms

Recommendations

A lower bound for the distributed Lovász local lemma

An optimal distributed (Δ+1)-coloring algorithm?

Distributed algorithms for the Lovász local lemma and graph coloring

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Funding Sources

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

HTML Format

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations