ABSTRACT
Consider an n-vertex graph G = (V,E) of maximum degree Δ, and suppose that each vertex v ∈ V hosts a processor. The processors are allowed to communicate only with their neighbors in G. The communication is synchronous, i.e., it proceeds in discrete rounds.
In the distributed vertex coloring problem the objective is to color G with Δ + 1, or slightly more than Δ + 1, colors using as few rounds of communication as possible. (The number of rounds of communication will be henceforth referred to as running time. Efficient randomized algorithms for this problem are known for more than twenty years [1, 19]. Specifically, these algorithms produce a Δ + 1)-coloring within O(log n) time, with high probability. On the other hand, the best known deterministic algorithm that requires polylogarithmic time employs O(Δ2) colors. This algorithm was devised in a seminal FOCS'87 paper by Linial [16]. Its running time is O(log* n). In the same paper Linial asked whether one can color with significantly less than Δ2 colors in deterministic polylogarithmic time. By now this question of Linial became one of the most central long-standing open questions in this area.
In this paper we answer this question in the affirmative, and devise a deterministic algorithm that employs Δ1+o(1) colors, and runs in polylogarithmic time. Specifically, the running time of our algorithm is O(f(Δ) log Δ log n, for an arbitrarily slow-growing function f(Δ) = ω(1). We can also produce O(Δ1 + η)-coloring in O(log Δ log n)-time, for an arbitrarily small constant η > 0, and O(Δ)-coloring in O(Δε log n) time, for an arbitrarily small constant ε > 0. Our results are, in fact, far more general than this. In particular, for a graph of arboricity a, our algorithm produces an O(a1 + η)-coloring, for an arbitrarily small constant η > 0, in time O(log a log n).
- 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 ScholarDigital Library
- B. Awerbuch, A. V. Goldberg, M. Luby, and S. Plotkin. Network decomposition and locality in distributed computation. In Proc. of the 30th Symposium on Foundations of Computer Science, pages 364--369, 1989. Google ScholarDigital Library
- L. Barenboim, and M. Elkin. Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition. In Proc. of the 27th ACM Symp. on Principles of Distributed Computing, pages 25--34, 2008. Google ScholarDigital Library
- L. Barenboim, and M. Elkin. Distributed (Δ + 1)-coloring in linear (in Δ) time. In Proc. of the 41th ACM Symp. on Theory of Computing, pages 111--120, 2009. Google ScholarDigital Library
- L. Barenboim, and M. Elkin. Distributed (Δ + 1)-coloring in linear (in Δ) time. http://arXiv.org/abs/0812.1379v2, 2008.Google Scholar
- L. Cowen, R. Cowen, and D. Woodall. Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valence. Journal of Graph Theory, 10:187--195, 1986.Google ScholarCross Ref
- R. Cole, and U. Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control, 70(1):32--53, 1986. Google ScholarDigital Library
- D. Eppstein. Arboricity and bipartite subgraph listing algorithms. Information Processing Letters, 51(4):207--211, 1994. Google ScholarDigital Library
- A. Goldberg, and S. Plotkin. Efficient parallel algorithms for (Δ + 1)- coloring and maximal independent set problem. In Proc. 19th ACM Symposium on Theory of Computing, pages 315--324, 1987.Google Scholar
- A. Goldberg, S. Plotkin, and G. Shannon. Parallel symmetry-breaking in sparse graphs. SIAM Journal on Discrete Mathematics, 1(4):434--446, 1988. Google ScholarDigital Library
- F. Harary, and K. Jones. Conditional colorability II: Bipartite variations. Congressus Numer, 50:205--218, 1985.Google Scholar
- Ö. Johansson. Simple distributed (Δ + 1)-coloring of graphs. Information Processing Letters, 70(5):229--232, 1999. Google ScholarDigital Library
- K. Kothapalli, C. Scheideler, M. Onus, and C. Schindelhauer. Distributed coloring in O(&38730;log n) bit rounds. In Proc. of the 20th International Parallel and Distributed Processing Symposium, 2006. Google ScholarDigital Library
- F. Kuhn. Weak graph colorings: distributed algorithms and applications. In proc. of the 21st ACM Symposium on Parallel Algorithms and Architectures, pages (138--144) February 2009. Google ScholarDigital Library
- F. Kuhn, and R. Wattenhofer. On the complexity of distributed graph coloring. In Proc. of the 25th ACM Symp. on Principles of Distributed Computing, pages 7--15, 2006. Google ScholarDigital Library
- N. Linial. Distributive graph algorithms: Global solutions from local data In Proc. of the 28th Annual Symp. on Foundation of Computer Science, pages 331--335, 1987. Google ScholarDigital Library
- N. Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193--201, 1992. Google ScholarDigital Library
- N. Linial and M. Saks. Low diameter graph decomposition. Combinatorica 13: 441--454, 1993.Google ScholarCross Ref
- M. Luby. A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing, 15:1036--1053, 1986. Google ScholarDigital Library
- C. Nash-Williams. Decompositions of finite graphs into forests. J. London Math, 39:12, 1964.Google ScholarCross Ref
- D. Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000. Google ScholarDigital Library
- A. Panconesi, and A. Srinivasan. On the complexity of distributed network decomposition. Journal of Algorithms, 20(2):581--592, 1995. Google ScholarDigital Library
Index Terms
- Deterministic distributed vertex coloring in polylogarithmic time
Recommendations
Deterministic Distributed Vertex Coloring in Polylogarithmic Time
Consider an n-vertex graph G = (V, E) of maximum degree Δ, and suppose that each vertex v ∈ V hosts a processor. The processors are allowed to communicate only with their neighbors in G. The communication is synchronous, that is, it proceeds in discrete ...
Polylogarithmic-time deterministic network decomposition and distributed derandomization
STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of ComputingWe present a simple polylogarithmic-time deterministic distributed algorithm for network decomposition. This improves on a celebrated 2 O(√logn)-time algorithm of Panconesi and Srinivasan [STOC’92] and settles a central and long-standing question in ...
Distributed Edge Coloring in Time Polylogarithmic in Δ
PODC'22: Proceedings of the 2022 ACM Symposium on Principles of Distributed ComputingWe provide new deterministic algorithms for the edge coloring problem, which is one of the classic and highly studied distributed local symmetry breaking problems. As our main result, we show that a (2Δ - 1)-edge coloring can be computed in time poly ...
Comments