Weak graph colorings: distributed algorithms and applications

ABSTRACT

We study deterministic, distributed algorithms for two weak variants of the standard graph coloring problem. We consider defective colorings, i.e., colorings where nodes of a color class may induce a graph of maximum degree d for some parameter d>0. We also look at colorings where a minimum number of multi-chromatic edges is required. For an integer k>0, we call a coloring k-partially proper if every node v has at least min{k,deg(v)} neighbors with a different color. We show that for all d∈{1,...,Δ}, it is possible to compute a O(Δ²/d²)-coloring with defect d in time O(log*n) where Δ is the largest degree of the network graph. Similarly, for all k∈{1,...,Δ}, a k-partially proper O(k²)-coloring can be computed in O(log*n) rounds.

As an application of our weak defective coloring algorithm, we obtain a faster deterministic algorithm for the standard vertex coloring problem on graphs with moderate degrees. We show that in time O(Δ+log*n), a (Δ+1)-coloring can be computed, a task for which the best previous algorithm required time O(Δ*log(Δ) + log*n). The same result holds for the problem of computing a maximal independent set.

REFERENCES

• 1: J. Andrews and M. Jacobson. On a generalization of chromatic number. Congressus Numerantium, 47:33--48, 1985.
• 2: Baruch Awerbuch, Complexity of network synchronization, Journal of the ACM (JACM), v.32 n.4, p.804-823, Oct. 1985 [doi>10.1145/4221.4227]
• 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: Leonid Barenboim , Michael Elkin, Distributed (δ+1)-coloring in linear (in δ) time, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA [doi>10.1145/1536414.1536432]
• 6: 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]
• 7: 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.
• 8: Lenore Cowen , Wayne Goddard , C. Esther Jesurum, Defective coloring revisited, Journal of Graph Theory, v.24 n.3, p.205-219, March 1997 [doi>10.1002/(SICI)1097-0118(199703)24:3<205::AID-JGT2>3.0.CO;2-T]
• 9: 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
• 10: P. Erd&#337;s, P. Frankl, and Z. F&#252;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.
• 11: M. Frick. A survery of (m,k)-colorings. Annals of Discrete Mathematics, 55:45--58, 1993.
• 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 Numerantium, 50:205--218, 1985.
• 14: K. Kothapalli, M. Onus, C. Scheideler, and C. Schindelhauer. Distributed coloring in o(&#8730;log n) bit rounds. In Proc. of 20th IEEE Int. Parallel and Distributed Processing Symposium (IPDPS), 2006.
• 15: F. Kuhn. Local multicoloring algorithms: Computing a nearly-optimal TDMA schedule in constant time. In Proc. of 26th Symp. on Theoretical Aspects of Computer Science (STACS), 2009.
• 16: 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]
• 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: L. Lov&#225;sz. On decompositions of graphs. Studia Sci. Math. Hungar., 1:237--238, 1966.
• 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: 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]
• 24: 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]
• 25: D. Woodall. Improper colourings of graphs. In R. Nelson and R. Wilson, editors, Graph Colourings. Longman Scientific and Technical, 1990.

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:
deterministic symmetry breaking, distributed algorithms, graph coloring, locality