Improved Distributed Algorithms for the Lovász Local Lemma and Edge Coloring

Davies, Peter

Abstract

The Lovász Local Lemma is a classic result in probability theory that is often used to prove the existence of combinatorial objects via the probabilistic method. In its simplest form, it states that if we have n ‘bad events’, each of which occurs with probability at most p and is independent of all but d other events, then under certain criteria on p and d, all of the bad events can be avoided with positive probability. While the original proof was existential, there has been much study on the algorithmic Lovász Local Lemma: that is, designing an algorithm which finds an assignment of the underlying random variables such that all the bad events are indeed avoided. Notably, the celebrated result of Moser and Tardos [JACM ’10] also implied an efficient distributed algorithm for the problem, running in O(log2 n) rounds. For instances with low d, this was improved to O(d 2 + logO(1) log n) by Fischer and Ghaffari [DISC ’17], a result that has proven highly important in distributed complexity theory (Chang and Pettie [SICOMP ’19]). We give an improved algorithm for the Lovász Local Lemma, providing a trade-off between the strength of the criterion relating p and d, and the distributed round complexity. In particular, in the same regime as Fischer and Ghaffari’s algorithm, we improve the round complexity to O( d log d + logO(1) log n). At the other end of the trade-off, we obtain a logO(1) log n round complexity for a substantially wider regime than previously known. As our main application, we also give the first logO(1) log n-round distributed algorithm for the problem of ∆+o(∆)-edge coloring a graph of maximum degree ∆. This is an almost exponential improvement over previous results: no prior logo(1) n-round algorithm was known even for 2∆ − 2-edge coloring.

Citation

Davies, P. (2023). Improved Distributed Algorithms for the Lovász Local Lemma and Edge Coloring. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (4273-4295). https://doi.org/10.1137/1.9781611977554.ch163

• Conference Name: ACM-SIAM Symposium on Discrete Algorithms (SODA23)
• Conference Location: Florence, Italy
• Start Date: Jan 22, 2023
• End Date: Jan 25, 2023
• Acceptance Date: Oct 17, 2023
• Online Publication Date: Jan 16, 2023
• Publication Date: Jan 16, 2023
• Deposit Date: Nov 4, 2022
• Publicly Available Date: Jul 19, 2023
• Pages: 4273-4295
• Book Title: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
• DOI: https://doi.org/10.1137/1.9781611977554.ch163