Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

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

  • Published:
Distributed Computing Aims and scope Submit manuscript

Abstract

The Lovász local lemma (LLL), introduced by Erdős and Lovász 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 works of Alon (Random Struct Algorithms 2(4):367–378, 1991) and Beck (Random Struct Algorithms 2(4):343–365, 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 (J ACM 57(2):11, 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(\log ^2 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 \(epd^2 < 1\) we give a truly simple LLL algorithm running in \(O(\log _{1/epd^2} n)\) rounds. Under the weaker condition \(ep(d+1) < 1\), we give a slightly slower algorithm running in \(O(\log ^2 d\cdot \log _{1/ep(d+1)} n)\) rounds. Furthermore, we give an algorithm that runs in sublogarithmic rounds under the condition \(p\cdot 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 \({\varOmega }(\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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

Notes

  1. Note that \(\log _{1/ep(d+1)} n\) could be sublogarithmic or superlogarithmic depending on how close \(ep(d+1)\) is to 0 or 1.

  2. These MIS algorithms are significantly more complex than Luby’s and use larger messages.

  3. Suppose H is both the distributed network and the graph to be colored. When invoking the LLL, the dependency graph \(G_{\mathcal {A}}\) is not identical to H. Typically bad events in \(\mathcal {A}\) are associated with H-vertices and two bad events are adjacent in \(G_{\mathcal {A}}\) only if the corresponding vertices are at distance O(1) in H. Thus, a distributed LLL algorithm for \(G_{\mathcal {A}}\) can be simulated in H with an O(1) slowdown.

  4. We slightly abuse the notation that when conditioning on the random variable \(X_i\), it means \(X_i\) may take arbitrary values, whereas when conditioning on the event \(\mathcal {E}_i\), it means that \(\mathcal {E}_i\) happens.

References

  1. Alon, N.: A parallel algorithmic version of the local lemma. Random Struct. Algorithms 2(4), 367–378 (1991)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  3. Alon, N., Krivelevich, M., Sudakov, B.: Coloring graphs with sparse neighborhoods. J. Comb. Theory Ser. B 77(1), 73–82 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  4. Barenboim, L., Elkin, M.: Distributed Graph Coloring: Fundamentals and Recent Developments Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool, San Rafael (2013)

    MATH  Google Scholar 

  5. Barenboim, L., Elkin, M., Kuhn, F.: Distributed \({({\varDelta }+1)}\)-coloring in linear (in \({\varDelta }\)) time. SIAM J. Comput. 43(1), 72–95 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  6. Barenboim, L., Elkin, M., Pettie, S., Schneider, J.: The locality of distributed symmetry breaking. J. ACM 63(3), 1–20 (2016)

  7. Beck, J.: An algorithmic approach to the Lovász local lemma. I. Random Struct. Algorithms 2(4), 343–365 (1991)

    Article  MATH  Google Scholar 

  8. Brandt, S., Fischer, O., Hirvonen, J., Keller, B., Lempiäinen, T., Rybicki, J., Suomela, J., Uitto, J.: A lower bound for the distributed lovász local lemma. In: Proceedings of 48th ACM Symposium on Theory of Computing (STOC), pp. 479–488 (2016)

  9. Chandrasekaran, K., Goyal, N., Haeupler, B.: Deterministic algorithms for the Lovász local lemma. SIAM J. Comput. 42(6), 2132–2155 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  10. Chang, Y., Kopelowitz, T., Pettie, S.: An exponential separation between randomized and deterministic complexity in the LOCAL model. In: Proceedings of 57th Symposium on Foundations of Computer Science (FOCS), pp. 195–197 (2016)

  11. Czumaj, A., Scheideler, C.: A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (extended abstract). In: Proceedings of 32nd ACM Symposium on Theory of Computing (STOC), pp. 38–47 (2000)

  12. Dubhashi, D., Grable, D.A., Panconesi, A.: Near-optimal, distributed edge colouring via the nibble method. Theor. Comput. Sci. 203(2), 225–251 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  13. Elkin, M., Pettie, S., Su, H.-H.: (\(2{\varDelta }-1\))-edge-coloring is much easier than maximal matching in the distributed setting. In: Proceedings of 26th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 355–370 (2015)

  14. Erdős, P., Lovász, L.: Problems and results on 3-chromatic hypergraphs and some related questions. In: Hanjal, A., Rado, R., Sós, V.T. (eds.) Infinite and Finite Sets, vol. 11, pp. 609–627. North-Holland, Amsterdam (1975)

    Google Scholar 

  15. Ghaffari, M.: An improved distributed algorithm for maximal independent set. In: Proceedings of 27th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 270–277 (2016)

  16. Haeupler, B., Saha, B., Srinivasan, A.: New constructive aspects of the Lovász local lemma. J. ACM 58(6), 28 (2011)

    Article  MATH  Google Scholar 

  17. Harris, D.G.: Lopsidependency in the Moser–Tardos framework: beyond the lopsided Lovász local lemma. In: Proceedings of 26th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1792–1808 (2015)

  18. Harris, D.G., Srinivasan, A.: The Moser-Tardos framework with partial resampling. In: Proceedings of 54th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 469–478 (2013)

  19. Harris, D.G., Srinivasan, A.: A constructive algorithm for the Lovász local lemma on permutations. In: Proceedings of 25th ACM-SIAM Symposium on Discrete Algorithms (SODA) pp. 907–925 (2014)

  20. Haxell, P.E.: A note on vertex list colouring. Comb. Probab. Comput. 10(4), 345–347 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  21. Hind, H., Molloy, M., Reed, B.: Colouring a graph frugally. Combinatorica 17(4), 469–482 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  22. Kolipaka, K., Szegedy, M.: Moser and Tardos meet Lovász. In: Proceedings 43rd ACM Symposium on Theory of Computing (STOC), pp. 235–244 (2011)

  23. Kuhn, F., Moscibroda, T., Wattenhofer, R.: Local computation: lower and upper bounds. J. ACM 63(2), 17 (2016)

    Article  MathSciNet  Google Scholar 

  24. Kuhn, F., Wattenhofer, R.: On the complexity of distributed graph coloring. In: Proceedings 25th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 7–15 (2006)

  25. Levi, R., Rubinfeld, R., Yodpinyanee, A.: Local computation algorithms for graphs of non-constant degrees. Algorithmica, pp. 1–24 (2016)

  26. Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193–201 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  27. Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15(4), 1036–1053 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  28. Molloy, M., Reed, B.: Further algorithmic aspects of the local lemma. In: Proceedings of 30th ACM Symposium on Theory of Computing (STOC), pp. 524–529 (1998)

  29. Molloy, M., Reed, B.: Graph Colouring and the Probabilistic Method. Algorithms and Combinatorics. Springer, Berlin (2001)

    MATH  Google Scholar 

  30. Molloy, M., Reed, B.: Asymptotically optimal frugal colouring. J. Comb. Theory Ser. B 100(2), 226–246 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  31. Moser, R.A.: Derandomizing the Lovász local lemma more effectively. CoRR, abs/0807.2120 (2008)

  32. Moser, R.A.: A constructive proof of the Lovász local lemma. In: Proceedings of 41st ACM Symposium on Theory of Computing (STOC), pp. 343–350 (2009)

  33. Moser, R.A., Tardos, G.: A constructive proof of the general Lovász local lemma. J. ACM 57(2), 11 (2010)

    Article  MATH  Google Scholar 

  34. Pegden, W.: An extension of the Moser–Tardos algorithmic local lemma. SIAM J. Discrete Math. 28(2), 911–917 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  35. Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, Philadelphia (2000)

    Book  Google Scholar 

  36. Pemmaraju, S., Srinivasan, A.: The randomized coloring procedure with symmetry-breaking. In: Proceedings of 35th Int’l Colloq. on Automata, Languages, and Programming (ICALP), pp. 306–319 (2008)

  37. Pettie, S., Su, H.-H.: Fast distributed coloring algorithms for triangle-free graphs. In: Proceedings of 40th Int’l Colloq. on Automata, Languages, and Programming (ICALP), pp. 687–699, (2013)

  38. Reed, B.: The list colouring constants. J. Graph Theory 31(2), 149–153 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  39. Reed, B., Sudakov, B.: Asymptotically the list colouring constants are 1. J. Comb. Theory Ser. B 86(1), 27–37 (2002)

  40. Schneider, J., Wattenhofer, R.: A new technique for distributed symmetry breaking. In: Proceedings of 29th ACM Symposium on Principles of Distributed Computing (PODC), pp. 257–266 (2010)

  41. Spencer, J.: Asymptotic lower bounds for Ramsey functions. Discret. Math. 20, 69–76 (1977)

    Article  MathSciNet  MATH  Google Scholar 

  42. Srinivasan, A.: Improved algorithmic versions of the Lovász local lemma. In: Proceedings of 19th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 611–620 (2008)

Download references

Acknowledgements

Thanks Mohsen Ghaffari for pointing out that by iteratively applying LLL, the range of f can be improved from \({\varOmega }(\log {\varDelta })\) to any positive integer for f-defective, \(O({\varDelta }/f)\)-colorings.

Author information

Authors and Affiliations

  1. Academia Sinica, Taipei, Taiwan

    Kai-Min Chung

  2. University of Michigan, Ann Arbor, MI, USA

    Seth Pettie

  3. MIT, Cambridge, MA, USA

    Hsin-Hao Su

Authors
  1. Kai-Min Chung
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Seth Pettie
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Hsin-Hao Su
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hsin-Hao Su.

Additional information

A preliminary version of this paper appeared in the 33rd Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC). Pettie and Su are supported by NSF Grants CCF-0746673, CCF-1217338, CNS-1318294, CCF-1514383, and a grant from the US-Israel Binational Science Foundation. Part of the work was done while visiting MADALGO at Aarhus University, supported by Danish National Research Foundation Grant DNRF84. Chung was supported by NSF Grants CNS-1217821, CCF-1214844, and R. Pass’s Sloan Fellowship.

Appendix: Tools

Appendix: Tools

Lemma 18

(Chernoff Bound) Let \(X_1,\dots , X_n\) be indicator variables such that \(\Pr (X_i=1) = p\). Let \(X = \sum _{i=1}^{n} X_i\). Then, for \(\delta > 0\):

$$\begin{aligned}&\Pr (X\ge (1+\delta ){\text {E}}[X])< \left[ \frac{e^{\delta }}{(1+\delta )^{(1+\delta )}} \right] ^{{\text {E}}[X]}\\&\quad \Pr (X\le (1-\delta ){\text {E}}[X]) < \left[ \frac{e^{\delta }}{(1-\delta )^{(1-\delta )}} \right] ^{{\text {E}}[X]} \end{aligned}$$

The two bounds above imply that for \(0< \delta < 1\), we have:

$$\begin{aligned}&\Pr (X\ge (1+\delta ){\text {E}}[X])< e^{-\delta ^2 {\text {E}}[X] / 3} \\&\quad \Pr (X\le (1-\delta ){\text {E}}[X]) < e^{-\delta ^2 {\text {E}}[X] / 2}. \end{aligned}$$

Lemma 19

Let \(\mathcal {E}_1, \ldots , \mathcal {E}_n\) be (likely) events and \(X_1, \ldots , X_n\) be indicator variables such that for each \(1 \le i \le n\) and \(X = \sum _{i=1}^{n} X_i\),

$$\begin{aligned} \max _{\varvec{X}_{i-1}}\Pr (X_i \mid \varvec{X}_{i-1}, \mathcal {E}_1,\ldots \mathcal {E}_i) \le p \end{aligned}$$

where \(\varvec{X}_i\) denotes the shorthand for \((X_1,\ldots ,X_i)\).Footnote 4 Then for \(\delta > 0\):

$$\begin{aligned} \Pr \left( (X >(1+\delta )np) \cap \left( \bigcap _{i} \mathcal {E}_i\right) \right)&\le \left[ \frac{e^{\delta }}{(1+\delta )^{(1+\delta )}} \right] ^{np} \end{aligned}$$

and thus by the union bound,

$$\begin{aligned} \Pr (X >(1+\delta )np)&\le \left[ \frac{e^{\delta }}{(1+\delta )^{(1+\delta )}} \right] ^{np} + \sum _{i} \Pr (\overline{\mathcal {E}_i}). \end{aligned}$$

Proof

For now let us treat \(\mathcal {E}_i\) as 0/1 random variables and let \(\mathcal {E} = \prod _i \mathcal {E}_i\). For any \(t>0\),

$$\begin{aligned}&\Pr \left( (X >(1+\delta )np) \cap \left( \bigcap _{i} \mathcal {E}_i\right) \right) \end{aligned}$$
(6)
$$\begin{aligned}&\quad = \Pr \left( \left( \prod _{i=1}^{n} \mathcal {E}_i \right) \cdot \exp (tX) > \exp (t(1+\delta )np)\right) \nonumber \\&\quad \le \frac{{\text {E}}\left[ \left( \prod _{i=1}^{n} \mathcal {E}_i\right) \cdot \exp (tX)\right] }{\exp (t(1+\delta )np)} \nonumber \\&\quad = \frac{{\text {E}}\left[ \left( \prod _{i=1}^{n} \mathcal {E}_i \cdot \exp (tX_i) \right) \right] }{\exp (t(1+\delta )np)} \end{aligned}$$
(7)

We will show by induction that

$$\begin{aligned} {\text {E}}\left[ \left( \prod _{i=1}^{k} \mathcal {E}_i \exp (tX_i) \right) \right] \le (1+p(e^t - 1))^k \end{aligned}$$

When \(k = 0\), it is trivial that \({\text {E}}[\mathcal {E}] \le 1\).

$$\begin{aligned}&{\text {E}}\left[ \left( \prod _{i=1}^{k} \mathcal {E}_i \exp (tX_i) \right) \right] \\&\quad \le {\text {E}}\left[ \left( \prod _{i=1}^{k-1} \mathcal {E}_i \exp (tX_i) \right) \right. \\&\qquad \left. \cdot {\text {E}}\left[ \mathcal {E}_k \exp (tX_k) \mid \varvec{X_{i-1}}, \mathcal {E}_1, \ldots , \mathcal {E}_{k-1}\right] \right] \\&\quad = {\text {E}}\left[ \left( \prod _{i=1}^{k-1} \mathcal {E}_i \exp (tX_i) \right) \right. \\&\qquad \left. \cdot \Pr (\mathcal {E}_k) \cdot {\text {E}}\left[ \exp (tX_k) \mid \varvec{X_{i-1}}, \mathcal {E}_1, \ldots , \mathcal {E}_{k}\right] \right] \\&\quad \le {\text {E}}\left[ \left( \prod _{i=1}^{k-1} \mathcal {E}_i \exp (tX_i) \right) \right. \\&\qquad \left. \cdot {\text {E}}\left[ \exp (tX_k) \mid \varvec{X_{i-1}}, \mathcal {E}_1, \ldots , \mathcal {E}_{k}\right] \right] \\&\quad = {\text {E}}\left[ \left( \prod _{i=1}^{k-1} \mathcal {E}_i \exp (tX_i) \right) \right. \\&\qquad \left. \cdot (1+\Pr (X_k \mid \varvec{X}_{i-1},\mathcal {E}_1, \ldots , \mathcal {E}_k)(e^{t} - 1)) \right] \\&\quad \le {\text {E}}\left[ \left( \prod _{i=1}^{k-1} \mathcal {E}_i \exp (tX_i) \right) \cdot (1+p(e^{t} - 1) ) \right] \\&\quad = {\text {E}}\left[ \left( \prod _{i=1}^{k-1} \mathcal {E}_i \exp (tX_i) \right) \right] \cdot (1+p(e^{t} - 1)) \\&\quad \le (1+p(e^{t} - 1))^{k} \end{aligned}$$

Therefore, by (6),

$$\begin{aligned}&\Pr \left( (X >(1+\delta )np) \cap \left( \bigcap _{i} \mathcal {E}_i\right) \right) \\&\quad = \frac{{\text {E}}[\mathcal {E} \cdot \prod _{i=1}^{n} \exp (tX_i) ]}{\exp (t(1+\delta )np)} \\&\quad \le \frac{(1+p(e^t-1))^{n}}{\exp (t(1+\delta )np)} \\&\quad \le \frac{\exp (np(e^t - 1))}{\exp (t(1+\delta )np)} \\&\quad = \left[ \frac{\exp (\delta ) }{(1+\delta )^{1+\delta }} \right] ^{np}. \end{aligned}$$

The last equality follows from the standard derivation of Chernoff Bound by choosing \(t = \ln (1+\delta )\). \(\square \)

Corollary 5

Suppose that for any \(\delta > 0\),

$$\begin{aligned} \Pr \left( (X >(1+\delta )np) \cap \left( \bigcap _{i} \mathcal {E}_i\right) \right) \le \left[ \frac{e^{\delta }}{(1+\delta )^{(1+\delta )}} \right] ^{np} \end{aligned}$$

then for any \(M \ge np\) and \(0< \delta < 1\),

$$\begin{aligned} \Pr \left( (X > np + \delta M) \cap \left( \bigcap _{i} \mathcal {E}_i\right) \right)&\le \left[ \frac{e^{\delta }}{(1+\delta )^{(1+\delta )}} \right] ^{M} \\&\le e^{-\delta ^2M/3} \end{aligned}$$

Proof

Without loss of generality, assume \(M = tnp\) for some \(t \ge 1\), we have

$$\begin{aligned}&\Pr \left( (X > np + \delta M) \cap \left( \bigcap _{i} \mathcal {E}_i\right) \right) \\&\quad \le \left[ \frac{e^{t \delta }}{(1+t \delta )^{(1+t \delta )}} \right] ^{np} \\&\quad = \left[ \frac{e^{\delta }}{(1+t \delta )^{(1+t \delta )/t}} \right] ^{M} \\&\quad \le \left[ \frac{e^{\delta }}{(1+\delta )^{(1+\delta )}} \right] ^{M} \qquad \qquad \qquad \qquad \qquad \quad \qquad \quad \quad \qquad (*) \\&\quad \le e^{-\delta ^2 M/ 3} \quad \quad \qquad \frac{e^{\delta }}{(1+\delta )^{(1+\delta )}} \le e^{-\delta ^2 / 3} \hbox { for } 0< \delta < 1 \end{aligned}$$

Inequality (*) follows if \((1+t \delta )^{(1+t \delta )/t} \ge (1+\delta )^{(1+\delta )}\), or equivalently, \(((1+t \delta )/t) \ln (1+t \delta ) \ge (1+\delta ) \ln (1+\delta )\). Letting \(f(t) = ((1+t \delta )/t )\ln (1+t \delta ) - (1+\delta ) \ln (1+\delta )\), we have \(f'(t) = \frac{1}{t^2}\left( \delta t - \ln (1+\delta t) \right) \ge 0\) for \(t > 0\). Since \(f(1) = 0\) and \(f'(t) \ge 0\) for \(t > 0\), we must have \(f(t) \ge 0\) for \(t\ge 1\). \(\square \)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chung, KM., Pettie, S. & Su, HH. Distributed algorithms for the Lovász local lemma and graph coloring. Distrib. Comput. 30, 261–280 (2017). https://doi.org/10.1007/s00446-016-0287-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00446-016-0287-6

Keywords

Search

Navigation