More Web Proxy on the site http://driver.im/

article

Combinatorial algorithms for distributed graph coloring

Authors:

Leonid Barenboim,

Michael ElkinAuthors Info & Claims

Distributed Computing, Volume 27, Issue 2

Pages 79 - 93

https://doi.org/10.1007/s00446-013-0203-2

Published: 01 April 2014 Publication History

Abstract

Numerous problems in Theoretical Computer Science can be solved very efficiently using powerful algebraic constructions. Computing shortest paths, constructing expanders, and proving the PCP Theorem, are just few examples of this phenomenon. The quest for combinatorial algorithms that do not use heavy algebraic machinery, but are roughly as efficient, has become a central field of study in this area. Combinatorial algorithms are often simpler than their algebraic counterparts. Moreover, in many cases, combinatorial algorithms and proofs provide additional understanding of studied problems. In this paper we initiate the study of combinatorial algorithms for Distributed Graph Coloring problems. In a distributed setting a communication network is modeled by a graph $$G=(V,E)$$G=(V,E) of maximum degree $$\varDelta $$Δ. The vertices of $$G$$G host the processors, and communication is performed over the edges of $$G$$G. The goal of distributed vertex coloring is to color $$V$$V with $$(\varDelta + 1)$$(Δ+1) colors such that any two neighbors are colored with distinct colors. Currently, efficient algorithms for vertex coloring that require $$O(\varDelta + \log ^* n)$$O(Δ+logýn) time are based on the algebraic algorithm of Linial (SIAM J Comput 21(1):193---201, 1992) that employs set-systems. The best currently-known combinatorial set-system free algorithm, due to Goldberg et al. (SIAM J Discret Math 1(4):434---446, 1988), requires $$O(\varDelta ^2+\log ^*n)$$O(Δ2+logýn) time. We significantly improve over this by devising a combinatorial$$(\varDelta + 1)$$(Δ+1)-coloring algorithm that runs in $$O(\varDelta + \log ^* n)$$O(Δ+logýn) time. This exactly matches the running time of the best-known algebraic algorithm. In addition, we devise a tradeoff for computing $$O(\varDelta \cdot t)$$O(Δ·t)-coloring in $$O(\varDelta /t + \log ^* n)$$O(Δ/t+logýn) time, for almost the entire range $$1 < t < \varDelta $$1

References

[1]

Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput. 28(4), 1167---1181 (1999)

Digital Library

[2]

Ajtai, M.: Recursive construction for 3-regular expanders. Combinatorica 14(4), 379---416 (1994)

[3]

Alon, N.: Eigen-values and expanders. Combinatorica 6(2), 83---96 (1986)

Digital Library

[4]

Alon, N., Babai, L., Itai, A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. J Algorithms 7(4), 567---583 (1986)

Digital Library

[5]

Alon, N., Galil, Z., Margalit, O.: On the exponent of the all pairs shortest path problem. J. Comput. Syst. Sci. 54(2), 255---262 (1997)

Digital Library

[6]

Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of NP. J. ACM 45(1), 70---122 (1998)

Digital Library

[7]

Awerbuch, B., Goldberg, A.V., Luby, M., Plotkin, S.: Network decomposition and locality in distributed computation. In: Proceedings of the 30th IEEE Annual Symposium on Foundations of Computer, Science, pp. 364---369, October 1989

Digital Library

[8]

Barenboim, L., Dolev, S., Ostrovsky, R.: Deterministic and energy-optimal wireless synchronization. In: Proceedings of the 25th International Symposium on Distributed Computing, pp. 237---251 (2011)

Digital Library

[9]

Barenboim, L., Elkin, M.: Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition. In: Proceedings of the 27th ACM Symposium on Principles of, Distributed Computing, pp. 25---34 (2008)

Digital Library

[10]

Barenboim, L., Elkin, M.: Distributed $$({\varDelta }+1)$$(Δ+1)-coloring in linear (in $${\varDelta }$$Δ) time. In: Proceedings of the 41th ACM Symposium on Theory of Computing, pp. 111---120, 2009. See also http://arXiv.org/abs/0812.1379v2 (2008)

Digital Library

[11]

Barenboim, L., Elkin, M.: Deterministic distributed vertex coloring in polylogarithmic time. In: Proceedings of the 29th ACM Symposium on Principles of, Distributed Computing, pp. 410---419 (2010)

Digital Library

[12]

Baswana, S., Kavitha, T.: Faster algorithms for all-pairs approximate shortest paths in undirected graphs. SIAM J. Comput. 39(7), 2865---2896 (2010)

Digital Library

[13]

Ben-Aroya, A., Ta-Shma, A.: A combinatorial construction of almost-Ramanujan graphs using the zig-zag product. In: Proceedings of the 40th ACM Symposium on Theory of, Computing, pp. 325---334 (2008)

Digital Library

[14]

Bilu, Y., Linial, N.: Lifts, discrepancy and nearly optimal spectral gaps. Combinatorica 26(5), 495---519 (2006)

Digital Library

[15]

Bradonjić, M., Kohler, E., Ostrovsky, R.: Near-optimal radio use for wireless network synchronization. In: Proceedings of the 5th International Workshop on Algorithmic Aspects of Wireless Sensor, Networks, pp. 15---28 (2009)

Digital Library

[16]

Cole, R., Vishkin, U.: Deterministic coin tossing with applications to optimal parallel list ranking. Inf. Control 70(1), 32---53 (1986)

Digital Library

[17]

Dinur, I.: The PCP theorem by gap amplification. In: Proceedings of the 38th ACM Symposium on Theory of, Computing, pp. 241---250 (2006)

Digital Library

[18]

Dinur, I., Reingold, O.: Assignment testers: towards a combinatorial proof of the PCP theorem. SIAM J. Comput. 36(4), 975---1024 (2006)

Digital Library

[19]

Dor, D., Halperin, S., Zwick, U.: All pairs almost shortest paths. SIAM J. Comput. 29(5), 1740---1759 (2000)

Digital Library

[20]

Elkin, M.: Computing almost shortest paths. In: Proceedings of the 20th ACM Symposium on Principles of, Distributed Computing, pp. 53---62 (2001)

Digital Library

[21]

Elkin, M., Kortsarz, G.: Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem. In: Proceedings of the 34th ACM Symposium on Theory of, Computing, pp. 438---447 (2002)

Digital Library

[22]

Elkin, M., Kortsarz, G.: Sublogarithmic approximation for telephone multicast: path out of jungle. In: Proceedings of the 14th ACM-Siam Symposium on Discrete Algorithms, pp. 76---85 (2003)

Digital Library

[23]

Erd?s, P., Frankl, P., Füredi, Z.: Families of finite sets in which no set is covered by the union of $$r$$r others. Israel J. Math. 51, 79---89 (1985)

[24]

Feige, U., Goldwasser, S., Lovasz, L., Safra, S., Szegedy, M.: Interactive proofs and the hardness of approximating cliques. J. ACM 43(2), 268---292 (1996)

Digital Library

[25]

Galil, Z., Margalit, O.: All pairs shortest distances for graphs with small integer length edges. Inf. Comput. 134(2), 103---139 (1997)

Digital Library

[26]

Garay, J.A., Kutten, S., Peleg, D.: A sub-linear timedistributed algorithm for minimum-weight spanning trees. In: Proceedings of the 34th IEEE Annual Symposium on Foundations of Computer, Science, pp. 659---668 (1993)

Digital Library

[27]

Goldberg, A., Plotkin, S.: Efficient parallel algorithms for $$({\varDelta }+1)$$(Δ+1)-coloring and maximal independent set problem. In: Proceedings 19th ACM Symposium on Theory of, Computing, pp. 315---324 (1987)

[28]

Goldberg, A., Plotkin, S., Shannon, G.: Parallel symmetry-breaking in sparse graphs. SIAM J. Discret. Math. 1(4), 434---446 (1988)

Digital Library

[29]

Goldreich, O., Safra, S.: A combinatorial consistency lemma with application to proving the PCP theorem. SIAM J. Comput. 29(4), 1132---1154 (2000)

Digital Library

[30]

Kale, S., Seshadhri, C.: Combinatorial approximation algorithms for MaxCut using random walks. In: Proceedings of the 2nd Symposium on Innovations in Computer, Science, pp. 367---388 (2011)

[31]

Kothapalli, K., Scheideler, C., Onus, M., Schindelhauer, C.: Distributed coloring in $$O(\sqrt{\log n})$$O(logn) bit rounds. In: 20th International Parallel and Distributed Processing Symposium (2006)

Digital Library

[32]

Kuhn, F.: Weak graph colorings: distributed algorithms and applications. In: Proceedings of the 21st ACM Symposium on Parallel Algorithms and Architectures, pp. 138---144 (2009)

Digital Library

[33]

Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: Proceedings of the 23rd ACM Symposium on Principles of, Distributed Computing, pp. 300---309 (2004)

Digital Library

[34]

Kuhn, F., Moscibroda, T., Wattenhofer, R.: Local computation: lower and upper bounds. http://arXiv.org/abs/1011.5470 (2010)

[35]

Kuhn, F., Wattenhofer, R.: On the complexity of distributed graph coloring. In Proc. of the 25th ACM Symp. on Principles of, Distributed Computing, pp. 7---15 (2006)

Digital Library

[36]

Kutten, S., Peleg, D.: Fast distributed construction of small k-dominating sets and application. In: Proceedings of the 14th ACM Symposium on Principles of, Distributed Computing, pp. 238---249 (1995)

Digital Library

[37]

Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193---201 (1992)

Digital Library

[38]

Lubotzky, A., Philips, R., Sarnak, P.: Ramanujan graphs. Combinatorica 8, 261---277 (1988)

[39]

Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15, 1036---1053 (1986)

Digital Library

[40]

Margulis, G.A.: Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredaci Informatsii 24(1), 51---60 (1988)

[41]

Meir, O.: Combinatorial PCPs with efficient verifiers. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer, Science, pp. 463---471 (2009)

Digital Library

[42]

Morgenstern, M.: Existence and explicit constructions of q+1 regular Ramanujan graphs for every prime power q. J. Comb. Theory Ser. B 62(1), 44---62 (1994)

Digital Library

[43]

Oldham, J.: Combinatorial approximation algorithms for generalized flow problems. In: Proceedings of the 10th ACM-Siam Symposium on Discrete Algorithms, pp. 704---714 (1999)

Digital Library

[44]

Panconesi, A., Rizzi, R.: Some simple distributed algorithms for sparse networks. Distrib. Comput. 14(2), 97---100 (2001)

Digital Library

[45]

Panconesi, A., Srinivasan, A.: On the complexity of distributed network decomposition. J. Algorithms 20(2), 581---592 (1995)

Digital Library

[46]

Peleg, D.: Distributed computing: a locality-sensitive approach, chap. 8, pp. 91---102. SIAM (2000)

[47]

Pinsker, M.: On the complexity of a concentrator. In: Proceedings of the 7th International Teletrac Conference, pp. 318/1---318/4 (1973)

[48]

Reingold, O.: Undirected ST-connectivity in log-space. In: Proceedings of the 37th ACM Symposium on Theory of, Computing, pp. 376---385 (2005)

Digital Library

[49]

Reingold, O., Vadhan, S., Wigderson, A.: Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. In: Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer, Science, pp. 3---13 (2000)

Digital Library

[50]

Seidel, R.: On the all-pairs-shortest-path problem. In: Proceedings of the 24th ACM Symposium on Theory of, Computing, pp. 745---749 (1995)

Digital Library

[51]

Szegedy, M., Vishwanathan, S.: Locality based graph coloring. In: Proceedings 25th ACM Symposium on Theory of Computing, San Diego, CA, USA, pp. 201---207, May 1993

Digital Library

[52]

Schneider, J., Wattenhofer, R.: A new technique for distributed symmetry breaking. In: Proceedings of the 29th ACM Symposium on Principles of, Distributed Computing, pp. 257---266 (2010)

Digital Library

Cited By

Rachmut BZivan RYeoh WDignum FLomuscio AEndriss UNowé A(2021)Latency-Aware Local Search for Distributed Constraint OptimizationProceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3463952.3464071(1019-1027)Online publication date: 3-May-2021
https://dl.acm.org/doi/10.5555/3463952.3464071
Abboud ACensor-Hillel KKhoury SPaz A(2021)Smaller Cuts, Higher Lower BoundsACM Transactions on Algorithms10.1145/346983417:4(1-40)Online publication date: 4-Oct-2021
https://dl.acm.org/doi/10.1145/3469834
Miller APelc A(2017)Deterministic distributed construction of T-dominating sets in time TDiscrete Applied Mathematics10.1016/j.dam.2017.01.012222:C(172-178)Online publication date: 11-May-2017
https://dl.acm.org/doi/10.1016/j.dam.2017.01.012
Show More Cited By

Combinatorial algorithms for distributed graph coloring
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation

Recommendations

Distributed (δ+1)-coloring in linear (in δ) time
STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

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 ...
Distributed algorithms for the Lovász local lemma and graph coloring

The Lovász local lemma (LLL), introduced by Erdźs and Lovász in 1975, is a powerful tool of the probabilistic method that allows one to prove that a set of n "bad" events do not happen with non-zero probability, provided that the events have limited ...
Can We Break Symmetry with o(m) Communication?
PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing

We study the communication cost (or message complexity) of fundamental distributed symmetry breaking problems, namely, coloring and MIS. While significant progress has been made in understanding and improving the running time of such problems, much less ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Distributed Computing

Distributed Computing Volume 27, Issue 2

April 2014

66 pages

ISSN:0178-2770

Issue’s Table of Contents

Copyright © Copyright © 2014 Springer-Verlag Berlin Heidelberg.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 April 2014

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Rachmut BZivan RYeoh WDignum FLomuscio AEndriss UNowé A(2021)Latency-Aware Local Search for Distributed Constraint OptimizationProceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3463952.3464071(1019-1027)Online publication date: 3-May-2021
https://dl.acm.org/doi/10.5555/3463952.3464071
Abboud ACensor-Hillel KKhoury SPaz A(2021)Smaller Cuts, Higher Lower BoundsACM Transactions on Algorithms10.1145/346983417:4(1-40)Online publication date: 4-Oct-2021
https://dl.acm.org/doi/10.1145/3469834
Miller APelc A(2017)Deterministic distributed construction of T-dominating sets in time TDiscrete Applied Mathematics10.1016/j.dam.2017.01.012222:C(172-178)Online publication date: 11-May-2017
https://dl.acm.org/doi/10.1016/j.dam.2017.01.012
Métivier YRobson JZemmari A(2016)Randomised distributed MIS and colouring algorithms for rings with oriented edges in O ( log ź n ) bit roundsInformation and Computation10.1016/j.ic.2016.09.006251:C(208-214)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1016/j.ic.2016.09.006

View Options

View options

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents