Distributed (δ+1)-coloring in linear (in δ) time

ABSTRACT

The distributed (Δ + 1)-coloring problem is one of most fundamental and well-studied problems in Distributed Algorithms. Starting with the work of Cole and Vishkin in 86, there was a long line of gradually improving algorithms published. The current state-of-the-art running time is O(Δ log Δ + log* n), due to Kuhn and Wattenhofer, PODC'06. Linial (FOCS'87) has proved a lower bound of 1/2 log* n for the problem, and Szegedy and Vishwanathan (STOC'93) provided a heuristic argument that shows that algorithms from a wide family of locally iterative algorithms are unlikely to achieve running time smaller than Θ(Δ log Δ). We present a deterministic (Δ + 1)-coloring distributed algorithm with running time O(Δ) + 1/2 log* n. We also present a tradeoff between the running time and the number of colors, and devise an O(Δ • t)-coloring algorithm with running time O(Δ / t + log* n), for any parameter t, 1 < t ≤ Δ^1-ε, for an arbitrarily small constant ε, 0 < ε < 1. Our algorithm breaks the heuristic barrier of Szegedy and Vishwanathan, and achieves running time which is linear in the maximum degree Δ. On the other hand, the conjecture of Szegedy and Vishwanathan may still be true, as our algorithm is not from the family of locally iterative algorithms. On the way to this result we study a generalization of the notion of graph coloring, which is called defective coloring. In an m-defective p-coloring the vertices are colored with p colors so that each vertex has up to m neighbors with the same color. We show that an m-defective p-coloring with reasonably small m and p can be computed very efficiently. We also develop a technique to employ multiple defective colorings of various subgraphs of the original graph G for computing a (Δ+1)-coloring of G. We believe that these techniques are of independent interest.

REFERENCES

• 1: Noga Alon , László Babai , Alon Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, Journal of Algorithms, v.7 n.4, p.567-583, Dec. 1986 [doi>10.1016/0196-6774(86)90019-2]
• 2: J. Andrews, and M. Jacobson. On a generalization of a chromatic number. Congressus Numer, 47:33--48, 1985.
• 3: B. Awerbuch , M. Luby , A. V. Goldberg , S. A. Plotkin, Network decomposition and locality in distributed computation, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, p.364-369, October 30-November 01, 1989 [doi>10.1109/SFCS.1989.63504]
• 4: Leonid Barenboim , Michael Elkin, Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400757]
• 5: Richard Cole , Uzi Vishkin, Deterministic coin tossing with applications to optimal parallel list ranking, Information and Control, v.70 n.1, p.32-53, July 1986 [doi>10.1016/S0019-9958(86)80023-7]
• 6: 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.
• 7: L. J. Cowen , W. Goddard , C. E. Jesurum, Coloring with defect, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.548-557, January 05-07, 1997, New Orleans, Louisiana, United States
• 8: P. Erdos, P. Frankl, and Z. Füredi. Families of finite sets in which no set is covered by the union of r others. Israel Journal of Mathematics, 51:79--89, 1985.
• 9: M. Frick. A survey of (m,k)-colorings. Quo Vadis, Graph Theory?, volume 55 of Annals of Discrete Mathematics, pages 45--58, 1993.
• 10: Beat Gfeller , Elias Vicari, A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281111]
• 11: 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.
• 12: Andrew V. Goldberg , Serge A. Plotkin , Gregory E. Shannon, Parallel symmetry-breaking in sparse graphs, SIAM Journal on Discrete Mathematics, v.1 n.4, p.434-446, Nov. 1988 [doi>10.1137/0401044]
• 13: F. Harary, and K. Jones. Conditional colorability II: Bipartite variations. Congressus Numer, 50:205--218, 1985.
• 14: Öjvind Johansson, Simple distributed&Dgr; + 1-coloring of graphs, Information Processing Letters, v.70 n.5, p.229-232, June 21, 1999 [doi>10.1016/S0020-0190(99)00064-2]
• 15: F. Kuhn. Determinstic distributed algorithms for weak colorings. Manuscript, February 2009.
• 16: F. Kuhn, T. Moscibroda, T. Nieberg, and R. Wattenhofer. Fast Deterministic Distributed Maximal Independent Set Computation on Growth--Bounded Graphs. In 19th International Symposium on Distributed Computing, pages 273--287, 2005.
• 17: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, What cannot be computed locally!, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011811]
• 18: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, On the locality of bounded growth, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073826]
• 19: Fabian Kuhn , Roger Wattenhofer, On the complexity of distributed graph coloring, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146387]
• 20: Nathan Linial, Distributive graph algorithms Global solutions from local data, Proceedings of the 28th Annual Symposium on Foundations of Computer Science, p.331-335, October 12-14, 1987 [doi>10.1109/SFCS.1987.20]
• 21: Nathan Linial, Locality in distributed graph algorithms, SIAM Journal on Computing, v.21 n.1, p.193-201, Feb. 1992 [doi>10.1137/0221015]
• 22: Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.15 n.4, p.1036-1055, Nov. 1986 [doi>10.1137/0215074]
• 23: A. Mayer, M. Naor, and L. Stockmeryer. Local computations on static and dynamic graphs In Proc. of the 3rd Israel Symp. on the Theory of Computing and Systems, pages 268--278, 1995.
• 24: Alessandro Panconesi , Romeo Rizzi, Some simple distributed algorithms for sparse networks, Distributed Computing, v.14 n.2, p.97-100, April 2001 [doi>10.1007/PL00008932]
• 25: A. Panconesi, and A. Srinivasan. On the complexity of distributed network decomposition. Journal of Algorithms, 20(2):581--592, 1995.
• 26: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 27: S. Plotkin. Graph-Theoretic Techniques for Parallel, Distributed, and Sequential Computation. Doctoral thesis. MIT Cambridge lab for computer science, 1988.
• 28: Johannes Schneider , Roger Wattenhofer, A log-star distributed maximal independent set algorithm for growth-bounded graphs, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400758]
• 29: Márió Szegedy , Sundar Vishwanathan, Locality based graph coloring, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.201-207, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167156]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms

Keywords:
coloring, defective-coloring, distributed algorithms