Distributed Algorithms for the Lovasz Local Lemma and Graph Coloring

The Lovasz Local Lemma (LLL), introduced by Erd}os and Lovasz in 1975, is a powerful tool of the probabilistic method that allows one to prove that a set of n \bad" events do not happen with non-zero probability, provided that the events have limited dependence. However, the LLL itself does not suggest how to find a point avoiding all bad events. Since the work of Beck (1991) there has been a sustained effort to find a constructive proof (i.e. an algorithm) for the LLL or weaker versions of it. In a major breakthrough Moser and Tardos (2010) showed that a point avoiding all bad events can be found efficiently. They also proposed a distributed/parallel version of their algorithm that requires O (log2 n) rounds of communication in a distributed network. In this paper we provide two new distributed algorithms for the LLL that improve on both the efficiency and simplicity of the Moser-Tardos algorithm. For clarity we express our results in terms of the symmetric LLL though both algorithms deal with the asymmetric version as well. Let p bound the probability of any bad event and d be the maximum degree in the dependency graph of the bad events. When epd2 < 1 we give a truly simple LLL algorithm running in O(log 1=epd2 n) rounds. Under the tighter condition ep(d + 1) < 1, we give a slightly slower algorithm running in O(log2 d . log 1=ep(d+1) n) rounds. Furthermore, we give an algorithm that runs in sublogarithmic rounds under the condition p . f (d) < 1, where f (d) is an exponential function of d. Although the conditions of the LLL are locally verifiable, we prove that any distributed LLL algorithm requires Omega(log* n) rounds. In many graph coloring problems the existence of a valid coloring is established by one or more applications of the LLL. Using our LLL algorithms, we give logarithmic-time distributed algorithms for frugal coloring, defective coloring, coloring girth-4 (triangle-free) and girth-5 graphs, edge coloring, and list coloring.