Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Coloring the nodes of a graph with a small number of colors is one of the most fundamental problems in theoretical computer science. In this paper, we study graph coloring in a distributed setting. Processors of a distributed system are nodes of an undirected graph G. There is an edge between two nodes whenever the corresponding processors can directly communicate with each other. We assume that distributed coloring algorithms start with an initial m-coloring of G. In the paper, we prove new strong lower bounds for two special kinds of coloring algorithms. For algorithms which run for a single communication round---i.e., every node of the network can only send its initial color to all its neighbors---, we show that the number of colors of the computed coloring has to be at least Ω(Δ²/log² Δ+ log log m). If such one-round algorithms are iteratively applied to reduce the number of colors step-by-step, we prove a time lower bound of Ω(Δ/log² Δ+ log*m) to obtain an O(Δ)-coloring. The best previous lower bounds for the two types of algorithms are Ω(log log m) and Ω(log*m), respectively.

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: B. Awerbuch, A. V. Goldberg, M. Luby, and S. A. Plotkin. Network decomposition and locality in distributed computation. In Proc. of the 30th Symposium on Foundations of Computer Science (FOCS), pages 364--369, 1989.
• 3: Mihir Bellare , Oded Goldreich , Madhu Sudan, Free Bits, PCPs, and Nonapproximability---Towards Tight Results, SIAM Journal on Computing, v.27 n.3, p.804-915, June 1998 [doi>10.1137/S0097539796302531]
• 4: V. Chvátal. A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 4(3), 1979.
• 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: Gianluca De Marco , Andrzej Pelc, Fast distributed graph coloring with O(&Dgr;) colors, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.630-635, January 07-09, 2001, Washington, D.C., United States
• 7: Michael Elkin, Distributed approximation: a survey, ACM SIGACT News, v.35 n.4, December 2004 [doi>10.1145/1054916.1054931]
• 8: P. Erdős, 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: Uriel Feige , Joe Kilian, Zero knowledge and the chromatic number, Journal of Computer and System Sciences, v.57 n.2, p.187-199, Oct. 1998 [doi>10.1006/jcss.1998.1587]
• 10: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 11: 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]
• 12: T. Hermann and S. Tixeuil. A distributed TDMA slot assignment algorithm for wireless sensor networks. In Proc. of 1st Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS), volume 3121 of Lecture Notes in Computer Science, pages 45--58, 2004.
• 13: Lujun Jia , Rajmohan Rajaraman , Torsten Suel, An efficient distributed algorithm for constructing small dominating sets, Distributed Computing, v.15 n.4, p.193-205, December 2002 [doi>10.1017/s00446-002-0078-0]
• 14: R. M. Karp. Reducibility among combinatorial problems. In Proc. of a Symposium on the Complexity of Computer Computations, pages 85--103, 1972.
• 15: F. Kuhn. The Price of Locality: Exploring the Complexity of Distributed Coordination Primitives. PhD thesis, ETH Zurich, August 2005.
• 16: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, The price of being near-sighted, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.980-989, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109666]
• 17: Nathan Linial, Locality in distributed graph algorithms, SIAM Journal on Computing, v.21 n.1, p.193-201, Feb. 1992 [doi>10.1137/0221015]
• 18: N. Linial and M. Saks. Low diameter graph decompositions. Combinatorica, 13(4):441--454, 1993.
• 19: 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]
• 20: Moni Naor , Larry Stockmeyer, What can be computed locally?, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.184-193, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167149]
• 21: Alessandro Panconesi , Aravind Srinivasan, On the complexity of distributed network decomposition, Journal of Algorithms, v.20 n.2, p.356-374, March 1996 [doi>10.1006/jagm.1996.0017]
• 22: A. Pelc. Personal communication.
• 23: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 24: S. Ramanathan, A unified framework and algorithm for channel assignment in wireless networks, Wireless Networks, v.5 n.2, p.81-94, March 1999 [doi>10.1023/A:1019126406181]

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; Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
chromatic number, distributed algorithms, graph coloring, locality, neighborhood graph, symmetry breaking