skip to main content
10.1145/1583991.1584032acmconferencesArticle/Chapter ViewAbstractPublication PagesspaaConference Proceedingsconference-collections
research-article

Weak graph colorings: distributed algorithms and applications

Published:11 August 2009Publication History

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(Δ2/d2)-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(k2)-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.Google ScholarGoogle Scholar
  2. B. Awerbuch. Complexity of network synchronization. Journal of the ACM, 32(4):804--823, 1985. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. B. Awerbuch, A. V. Goldberg, M. Luby, and S. A. Plotkin. Network decomposition and locality in distributed computation. In Proc. of 30th Symposium on Foundations of Computer Science (FOCS), pages 364--369, 1989. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. L. Barenboim and M. Elkin. Sublogarithmic distributed mis algorithm for sparse graphs using nash-williams decomposition. In Proc. of 27th ACM Symposium on Principles of Distributed Computing (PODC), 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. L. Barenboim and M. Elkin. Distributed (Δ+1)-coloring in linear (in Δ) time. In Proc. of the 41st ACM Symposium on Theory of Computing (STOC), 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. R. Cole and U. Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control, 70(1):32--53, 1986. Google ScholarGoogle ScholarDigital LibraryDigital Library
  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.Google ScholarGoogle ScholarCross RefCross Ref
  8. L. Cowen, W. Goddard, and C. Jesurum. Defective coloring revisitied. Journal of Graph Theory, 24(3):205--219, 1997. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. G. De Marco and A. Pelc. Fast distributed graph coloring with O(Δ) colors. In Proc. of 12th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 630--635, 2001. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. 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.Google ScholarGoogle ScholarCross RefCross Ref
  11. M. Frick. A survery of (m,k)-colorings. Annals of Discrete Mathematics, 55:45--58, 1993.Google ScholarGoogle ScholarCross RefCross Ref
  12. A. Goldberg, S. Plotkin, and G. Shannon. Parallel symmetry-breaking in sparse graphs. SIAM Journal on Discrete Mathematics, 1(4):434--446, 1988. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. F. Harary and K. Jones. Conditional colorability II: Bipartite variations. Congressus Numerantium, 50:205--218, 1985.Google ScholarGoogle Scholar
  14. K. Kothapalli, M. Onus, C. Scheideler, and C. Schindelhauer. Distributed coloring in o(√log n) bit rounds. In Proc. of 20th IEEE Int. Parallel and Distributed Processing Symposium (IPDPS), 2006. Google ScholarGoogle ScholarDigital LibraryDigital Library
  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.Google ScholarGoogle Scholar
  16. F. Kuhn and R. Wattenhofer. On the complexity of distributed graph coloring. In Proc. of 25th ACM Symposium on Principles of Distributed Computing (PODC), pages 7--15, 2006. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. N. Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193--201, 1992. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. L. Lovász. On decompositions of graphs. Studia Sci. Math. Hungar., 1:237--238, 1966.Google ScholarGoogle Scholar
  19. M. Luby. A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing, 15:1036--1053, 1986. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. M. Naor and L. Stockmeyer. What can be computed locally? In Proc. of 25th ACM Symposium on Theory of Computing (STOC), pages 184--193, 1993. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. A. Panconesi and A. Srinivasan. On the complexity of distributed network decomposition. Journal of Algorithms, 20(2):581--592, 1995. Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. A. Pelc. Personal communication.Google ScholarGoogle Scholar
  23. J. Schneider and R. Wattenhofer. A log-star distributed maximal independent set algorithm for growth-bounded graphs. In Proc. of 27th ACM Symposium on Principles of Distributed Computing (PODC), 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. M. Szegedy and S. Vishwanathan. Locality based graph coloring. In Proc. of the 25th ACM Symposium on Theory of Computing (STOC), pages 201--207, 1993. Google ScholarGoogle ScholarDigital LibraryDigital Library
  25. D. Woodall. Improper colourings of graphs. In R. Nelson and R. Wilson, editors, Graph Colourings. Longman Scientific and Technical, 1990.Google ScholarGoogle Scholar

Index Terms

  1. Weak graph colorings: distributed algorithms and applications

          Recommendations

          Comments

          Login options

          Check if you have access through your login credentials or your institution to get full access on this article.

          Sign in
          • Published in

            cover image ACM Conferences
            SPAA '09: Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures
            August 2009
            370 pages
            ISBN:9781605586069
            DOI:10.1145/1583991

            Copyright © 2009 ACM

            Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

            Publisher

            Association for Computing Machinery

            New York, NY, United States

            Publication History

            • Published: 11 August 2009

            Permissions

            Request permissions about this article.

            Request Permissions

            Check for updates

            Qualifiers

            • research-article

            Acceptance Rates

            Overall Acceptance Rate447of1,461submissions,31%

            Upcoming Conference

            SPAA '24

          PDF Format

          View or Download as a PDF file.

          PDF

          eReader

          View online with eReader.

          eReader