Distributed algorithms for the Lovász local lemma and graph coloring
Distributed algorithms for the Lovász local lemma and graph coloring
复制标题
DOI：
10.1007/s00446-016-0287-6
复制
发表时间：
2014-07
影响因子：
1.3
通讯作者：
Kai-Min Chung;Seth Pettie;Hsin-Hao Su
中科院分区：
文献类型：
--
作者：
Kai-Min Chung;Seth Pettie;Hsin-Hao Su
由Erdos和Lovasz于1975年提出的Lovasz局部引理（LLL）是概率方法的一个有力工具，它允许人们证明一组n个“坏”事件不以非零概率发生，只要事件具有有限的依赖性。然而，LLL本身并没有建议如何找到一个点，避免所有的坏事件。自Beck（1991）的工作以来，人们一直在努力寻找LLL或其较弱版本的构造性证明（即算法）。在一项重大突破中，Moser和Tardos（2010）表明可以有效地找到避免所有坏事件的点。他们还提出了一个分布式/并行版本的算法，需要O（log 2n）轮的通信在一个分布式network.In本文中，我们提供了两个新的分布式算法的LLL，提高了效率和简单性的Moser-Tardos算法。为了清楚起见，我们表示我们的结果的对称LLL虽然这两种算法处理的非对称版本以及。设p限制任何坏事件的概率，d是坏事件的依赖图中的最大度。当epd 2 < 1时，我们给出了一个真正简单的运行时间为O（log 1/epd 2n）的LLL算法。在更严格的条件ep（d+1）< 1下，我们给出了一个运行时间为O（log 2d <$log1/ep（d+1）n）轮的速度稍慢的算法.此外，我们还给出了一个在p ∈ f（d）< 1的条件下以次对数循环运行的算法，其中f（d）是d的指数函数。虽然LLL的条件是局部可验证的，但我们证明了任何分布式LLL算法都需要Ω（log* n）轮.在许多图着色问题中，有效着色的存在性是通过LLL的一个或多个应用来建立的.利用我们的LLL算法，我们给出了节俭着色，缺陷着色，着色围长-4（无三角形）和围长-5图，边着色和列表着色的时间分布算法。
The Lovasz Local Lemma (LLL), introduced by Erdos 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(log2n) 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(log1/epd2n) rounds. Under the tighter condition ep(d+1) < 1, we give a slightly slower algorithm running in O(log2d⋅ log1/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 Ω(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.