Document Open Access Logo

Improved Distributed Fractional Coloring Algorithms

Authors Alkida Balliu, Fabian Kuhn, Dennis Olivetti

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2021.18.pdf
  • Filesize: 0.72 MB
  • 23 pages

Document Identifiers

Author Details

Alkida Balliu
  • Gran Sasso Science Institute, L'Aquila, Italy
Fabian Kuhn
  • University of Freiburg, Germany
Dennis Olivetti
  • Gran Sasso Science Institute, L'Aquila, Italy

Cite As Get BibTex

Alkida Balliu, Fabian Kuhn, and Dennis Olivetti. Improved Distributed Fractional Coloring Algorithms. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 18:1-18:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.OPODIS.2021.18

Abstract

We prove new bounds on the distributed fractional coloring problem in the LOCAL model. A fractional c-coloring of a graph G = (V,E) is a fractional covering of the nodes of G with independent sets such that each independent set I of G is assigned a fractional value λ_I ∈ [0,1]. The total value of all independent sets of G is at most c, and for each node v ∈ V, the total value of all independent sets containing v is at least 1. Equivalently, fractional c-colorings can also be understood as multicolorings as follows. For some natural numbers p and q such that p/q ≤ c, each node v is assigned a set of at least q colors from {1,…,p} such that adjacent nodes are assigned disjoint sets of colors. The minimum c for which a fractional c-coloring of a graph G exists is called the fractional chromatic number χ_f(G) of G.
Recently, [Bousquet, Esperet, and Pirot; SIROCCO '21] showed that for any constant ε > 0, a fractional (Δ+ε)-coloring can be computed in Δ^{O(Δ)} + O(Δ⋅log^* n) rounds. We show that such a coloring can be computed in only O(log² Δ) rounds, without any dependency on n.
We further show that in O((log n)/ε) rounds, it is possible to compute a fractional (1+ε)χ_f(G)-coloring, even if the fractional chromatic number χ_f(G) is not known. That is, the fractional coloring problem can be approximated arbitrarily well by an efficient algorithm in the LOCAL model. For the standard coloring problem, it is only known that an O((log n)/(log log n))-approximation can be computed in polylogarithmic time in the LOCAL model. We also show that our distributed fractional coloring approximation algorithm is best possible. We show that in trees, which have fractional chromatic number 2, computing a fractional (2+ε)-coloring requires at least Ω((log n)/ε) rounds.
We finally study fractional colorings of regular grids. In [Bousquet, Esperet, and Pirot; SIROCCO '21], it is shown that in regular grids of bounded dimension, a fractional (2+ε)-coloring can be computed in time O(log^* n). We show that such a coloring can even be computed in O(1) rounds in the LOCAL model.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • distributed graph algorithms
  • distributed coloring
  • locality
  • fractional coloring

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. N. Alon, L. Babai, and A. Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. Journal of Algorithms, 7(4):567-583, 1986. Google Scholar
  2. Yves Aubry, Jean-Christophe Godin, and Olivier Togni. Every triangle-free induced subgraph of the triangular lattice is (5m, 2m)-choosable. Discret. Appl. Math., 166:51-58, 2014. Google Scholar
  3. B. Awerbuch, A. V. Goldberg, M. Luby, and S. A. Plotkin. Network decomposition and locality in distributed computation. In Proc. 30th IEEE Symp. on Foundations of Computer Science (FOCS), pages 364-369, 1989. Google Scholar
  4. Alkida Balliu, Sebastian Brandt, and Dennis Olivetti. Distributed lower bounds for ruling sets. In 61st IEEE Annual Symposium on Foundations of Computer Science, (FOCS), pages 365-376, 2020. Google Scholar
  5. L. Barenboim. Deterministic (Δ+ 1)-coloring in sublinear (in Δ) time in static, dynamic, and faulty networks. Journal of the ACM, 63(5):1-22, 2016. Google Scholar
  6. L. Barenboim and M. Elkin. Deterministic distributed vertex coloring in polylogarithmic time. In Proc. 29th Symp. on Principles of Distributed Computing (PODC), pages 410-419, 2010. Google Scholar
  7. L. Barenboim, M. Elkin, and C. Gavoille. A fast network-decomposition algorithm and its applications to constant-time distributed computation. In Proc. 22nd Coll. on Structural Information and Communication Complexity (SIROCCO), pages 209-223, 2015. Google Scholar
  8. L. Barenboim, M. Elkin, and U. Goldenberg. Locally-iterative distributed (Δ+1)-coloring below Szegedy-Vishwanathan barrier, and applications to self-stabilization and to restricted-bandwidth models. In Proc. 37th ACM Symp. on Principles of Distributed Computing (PODC), pages 437-446, 2018. Google Scholar
  9. L. Barenboim, M. Elkin, and F. Kuhn. Distributed (Δ+1)-coloring in linear (in Δ) time. SIAM Journal on Computing, 43(1):72-95, 2015. Google Scholar
  10. L. Barenboim, M. Elkin, S. Pettie, and J. Schneider. The locality of distributed symmetry breaking. Journal of the ACM, 63:20:1-20:45, 2016. Google Scholar
  11. Nicolas Bousquet, Louis Esperet, and Fraigniaudnçois Pirot. Distributed algorithms for fractional coloring. In Proc. 28th Coll. on Structural Information and Communication Complexity (SIROCCO), pages 15-30, 2021. Google Scholar
  12. S. Brandt, O. Fischer, J. Hirvonen, B. Keller, T. Lempiäinen, J. Rybicki, J. Suomela, and J. Uitto. A lower bound for the distributed Lovász local lemma. In Proc. 48th ACM Symp. on Theory of Computing (STOC), pages 479-488, 2016. Google Scholar
  13. Y.-J. Chang, W. Li, and S. Pettie. An optimal distributed (Δ + 1)-coloring algorithm? In Proc. 50th ACM Symp. on Theory of Computing (STOC), 2018. Google Scholar
  14. M. Elkin and O. Neiman. Distributed strong diameter network decomposition. In Proc. 35th ACM Symp. on Principles of Distributed Computing (PODC), pages 211-216, 2016. Google Scholar
  15. Michael Elkin, Seth Pettie, and Hsin-Hao Su. (2Δ - l)-edge-coloring is much easier than maximal matching in the distributed setting. In Proc. 26th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 355-370, 2015. Google Scholar
  16. Salwa Faour and Fabian Kuhn. Approximating Bipartite Minimum Vertex Cover in the CONGEST Model. In 24th International Conference on Principles of Distributed Systems (OPODIS), pages 29:1-29:16, 2021. Google Scholar
  17. P. Fraigniaud, M. Heinrich, and A. Kosowski. Local conflict coloring. In Proc. 57th IEEE Symp. on Foundations of Computer Science (FOCS), pages 625-634, 2016. Google Scholar
  18. M. Ghaffari, D. Harris, and F. Kuhn. On derandomizing local distributed algorithms. In Proc. 59th Annual Symposium on Foundations of Computer Science, (FOCS), pages 662-673, 2018. Google Scholar
  19. Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, and Yannic Maus. Improved distributed Δ-coloring. Distributed Comput., 34(4):239-258, 2021. Google Scholar
  20. Mohsen Ghaffari and Fabian Kuhn. Deterministic distributed vertex coloring: Simpler, faster, and without network decomposition. In Proc. 62nd IEEE Symp. on Foundations of Computer Science (FOCS), 2021. Google Scholar
  21. A. V. Goldberg, S. A. Plotkin, and G. E. Shannon. Parallel symmetry-breaking in sparse graphs. SIAM Journal on Discrete Mathematics, 1(4):434-446, 1988. Google Scholar
  22. Magnús M. Halldórsson, Alexandre Nolin, and Tigran Tonoyan. Ultrafast distributed coloring of high degree graphs. CoRR, abs/2105.04700, 2021. URL: http://arxiv.org/abs/2105.04700.
  23. D. G. Harris, J. Schneider, and H.-H. Su. Distributed (Δ+1)-coloring in sublogarithmic rounds. In Proc. 48th ACM Symp. on Theory of Computing (STOC), 2016. Google Scholar
  24. Henning Hasemann, Juho Hirvonen, Joel Rybicki, and Jukka Suomela. Deterministic local algorithms, unique identifiers, and fractional graph colouring. Theor. Comput. Sci., 610:204-217, 2016. Google Scholar
  25. Öjvind Johansson. Simple distributed Delta+1-coloring of graphs. Inf. Process. Lett., 70(5):229-232, 1999. Google Scholar
  26. K. Kothapalli, M. Onus, C. Scheideler, and C. Schindelhauer. Distributed coloring in O(√log n) bit rounds. In Proc. 20th IEEE Int. Parallel and Distributed Processing Symp. (IPDPS), 2006. Google Scholar
  27. F. Kuhn. Local multicoloring algorithms: Computing a nearly-optimal TDMA schedule in constant time. In Proc. Symp. on Theoretical Aspects of Computer Science (STACS), pages 613-624, 2009. Google Scholar
  28. F. Kuhn. Faster deterministic distributed coloring through recursive list coloring. In Proc. 32st ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 1244-1259, 2020. Google Scholar
  29. F. Kuhn and R. Wattenhofer. On the complexity of distributed graph coloring. In Proc. 25th ACM Symp. on Principles of Distributed Computing (PODC), pages 7-15, 2006. Google Scholar
  30. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1996. Google Scholar
  31. N. Linial. Distributive graph algorithms - global solutions from local data. In Proc. 28th IEEE Symp. on Foundations of Computer Science (FOCS), pages 331-335, 1987. Google Scholar
  32. N. Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193-201, 1992. Google Scholar
  33. N. Linial and M. Saks. Low diameter graph decompositions. Combinatorica, 13(4):441-454, 1993. Google Scholar
  34. Alexander Lubotzky, Ralph Phillips, and Peter Sarnak. Ramanujan graphs. Comb., 8(3):261-277, 1988. Google Scholar
  35. M. Luby. A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing, 15:1036-1053, 1986. Google Scholar
  36. Y. Maus and T. Tonoyan. Local conflict coloring revisited: Linial for lists. In Proc. 34th Int. Symp. on Distributed Computing (DISC), pages 16:1-16:18, 2020. Google Scholar
  37. Yannic Maus. Distributed graph coloring made easy. In Proc. 33rd ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pages 362-372, 2021. Google Scholar
  38. Gary L Miller, Richard Peng, and Shen Chen Xu. Parallel graph decompositions using random shifts. In Proceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures, pages 196-203, 2013. Google Scholar
  39. Moni Naor. A lower bound on probabilistic algorithms for distributive ring coloring. SIAM J. on Discrete Math., 4(3):409-412, 1991. Google Scholar
  40. A. Panconesi and A. Srinivasan. Improved distributed algorithms for coloring and network decomposition problems. In Proc. 24th ACM Symp. on Theory of Computing (STOC), pages 581-592, 1992. Google Scholar
  41. A. Panconesi and A. Srinivasan. The local nature of Δ-coloring and its algorithmic applications. Combinatorica, 15(2):255-280, 1995. Google Scholar
  42. V. Rozhoň and M. Ghaffari. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In Proc. 52nd ACM Symp. on Theory of Computing (STOC), pages 350-363, 2020. Google Scholar
  43. Johannes Schneider, Michael Elkin, and Roger Wattenhofer. Symmetry breaking depending on the chromatic number or the neighborhood growth. Theor. Comput. Sci., 509:40-50, 2013. Google Scholar
  44. Johannes Schneider and Roger Wattenhofer. A new technique for distributed symmetry breaking. In Proc. 29th ACM Symp. on Principles of Distributed Computing (PODC), pages 257-266, 2010. Google Scholar
  45. M. Szegedy and S. Vishwanathan. Locality based graph coloring. In Proc. 25th ACM Symp. on Theory of Computing (STOC), pages 201-207, 1993. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact