On the complexity of distributed graph coloring

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. 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.
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. M. Bellare, O. Goldreich, and M. Sudan. Free bits, PCPs and non-approximability -- towards tight results. SIAM Journal on Computing, 27:804--915, 1998.
4. V. Chvátal. A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 4(3), 1979.
5. R. Cole and U. Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control, 70(1):32--53, 1986.
6. G. De Marco and A. Pelc. Fast distributed graph coloring with O(Δ) colors. In Proc. of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 630--635, 2001.
7. M. Elkin. Distributed approximation: A survey. ACM SIGACT News, 35(4):40--57, 2004.
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. U. Feige and J. Kilian. Zero knowledge and the chromatic number. Journal of Computer and System Sciences, 57:187--199, 1998.
10. M. R. Garey and D. S. Johnson. Computers and Intractability, A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979.
11. A. Goldberg, S. Plotkin, and G. Shannon. Parallel symmetry-breaking in sparse graphs. SIAM Journal on Discrete Mathematics, 1(4):434--446, 1988.
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. L. Jia, R. Rajaraman, and R. Suel. An efficient distributed algorithm for constructing small dominating sets. Distributed Computing, 15(4):193--205, 2002.
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. F. Kuhn, T. Moscibroda, and R. Wattenhofer. The price of being near-sighted. In Proc. of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006.
17. N. Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193--201, February 1992.
18. N. Linial and M. Saks. Low diameter graph decompositions. Combinatorica, 13(4):441--454, 1993.
19. M. Luby. A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing, 15:1036--1053, 1986.
20. M. Naor and L. Stockmeyer. What can be computed locally? In Proc. of the 25th Annual ACM Symposium on Theory of Computing (STOC), pages 184--193, 1993.
21. A. Panconesi and A. Srinivasan. On the complexity of distributed network decomposition. Journal of Algorithms, 20(2):581--592, 1995.
22. A. Pelc. Personal communication.
23. D. Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000.
24. S. Ramanathan. A unified framework and algorithm for channel assignment in wireless networks. Wireless Networks, 5:81--94, 1999.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms

      • Network flows

• Theory of computation

  • Design and analysis of algorithms

    • Graph algorithms analysis

      • Network flows

  • Randomness, geometry and discrete structures