Combinatorial algorithms for distributed graph coloring
Tóm tắt
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)$$
of maximum degree
$$\varDelta $$
. The vertices of
$$G$$
host the processors, and communication is performed over the edges of
$$G$$
. The goal of distributed vertex coloring is to color
$$V$$
with
$$(\varDelta + 1)$$
colors such that any two neighbors are colored with distinct colors. Currently, efficient algorithms for vertex coloring that require
$$O(\varDelta + \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)$$
time. We significantly improve over this by devising a combinatorial
$$(\varDelta + 1)$$
-coloring algorithm that runs in
$$O(\varDelta + \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)$$
-coloring in
$$O(\varDelta /t + \log ^* n)$$
time, for almost the entire range
$$1 < t < \varDelta $$
. We also compute a Maximal Independent Set in
$$O(\varDelta + \log ^* n)$$
time on general graphs, and in
$$O(\log n/ \log \log n)$$
time on graphs of bounded arboricity. Prior to our work, these results could be only achieved using algebraic techniques. We believe that our algorithms are more suitable for real-life networks with limited resources, such as sensor networks.
Tài liệu tham khảo
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)
Ajtai, M.: Recursive construction for 3-regular expanders. Combinatorica 14(4), 379–416 (1994)
Alon, N.: Eigen-values and expanders. Combinatorica 6(2), 83–96 (1986)
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)
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)
Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of NP. J. ACM 45(1), 70–122 (1998)
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
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)
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)
Barenboim, L., Elkin, M.: Distributed \(({\varDelta }+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)
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)
Baswana, S., Kavitha, T.: Faster algorithms for all-pairs approximate shortest paths in undirected graphs. SIAM J. Comput. 39(7), 2865–2896 (2010)
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)
Bilu, Y., Linial, N.: Lifts, discrepancy and nearly optimal spectral gaps. Combinatorica 26(5), 495–519 (2006)
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)
Cole, R., Vishkin, U.: Deterministic coin tossing with applications to optimal parallel list ranking. Inf. Control 70(1), 32–53 (1986)
Dinur, I.: The PCP theorem by gap amplification. In: Proceedings of the 38th ACM Symposium on Theory of, Computing, pp. 241–250 (2006)
Dinur, I., Reingold, O.: Assignment testers: towards a combinatorial proof of the PCP theorem. SIAM J. Comput. 36(4), 975–1024 (2006)
Dor, D., Halperin, S., Zwick, U.: All pairs almost shortest paths. SIAM J. Comput. 29(5), 1740–1759 (2000)
Elkin, M.: Computing almost shortest paths. In: Proceedings of the 20th ACM Symposium on Principles of, Distributed Computing, pp. 53–62 (2001)
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)
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)
Erdős, P., Frankl, P., Füredi, Z.: Families of finite sets in which no set is covered by the union of \(r\) others. Israel J. Math. 51, 79–89 (1985)
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)
Galil, Z., Margalit, O.: All pairs shortest distances for graphs with small integer length edges. Inf. Comput. 134(2), 103–139 (1997)
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)
Goldberg, A., Plotkin, S.: Efficient parallel algorithms for \(({\varDelta }+1)\)-coloring and maximal independent set problem. In: Proceedings 19th ACM Symposium on Theory of, Computing, pp. 315–324 (1987)
Goldberg, A., Plotkin, S., Shannon, G.: Parallel symmetry-breaking in sparse graphs. SIAM J. Discret. Math. 1(4), 434–446 (1988)
Goldreich, O., Safra, S.: A combinatorial consistency lemma with application to proving the PCP theorem. SIAM J. Comput. 29(4), 1132–1154 (2000)
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)
Kothapalli, K., Scheideler, C., Onus, M., Schindelhauer, C.: Distributed coloring in \(O(\sqrt{\log n})\) bit rounds. In: 20th International Parallel and Distributed Processing Symposium (2006)
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)
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)
Kuhn, F., Moscibroda, T., Wattenhofer, R.: Local computation: lower and upper bounds. http://arXiv.org/abs/1011.5470 (2010)
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)
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)
Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193–201 (1992)
Lubotzky, A., Philips, R., Sarnak, P.: Ramanujan graphs. Combinatorica 8, 261–277 (1988)
Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15, 1036–1053 (1986)
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)
Meir, O.: Combinatorial PCPs with efficient verifiers. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer, Science, pp. 463–471 (2009)
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)
Oldham, J.: Combinatorial approximation algorithms for generalized flow problems. In: Proceedings of the 10th ACM-Siam Symposium on Discrete Algorithms, pp. 704–714 (1999)
Panconesi, A., Rizzi, R.: Some simple distributed algorithms for sparse networks. Distrib. Comput. 14(2), 97–100 (2001)
Panconesi, A., Srinivasan, A.: On the complexity of distributed network decomposition. J. Algorithms 20(2), 581–592 (1995)
Peleg, D.: Distributed computing: a locality-sensitive approach, chap. 8, pp. 91–102. SIAM (2000)
Pinsker, M.: On the complexity of a concentrator. In: Proceedings of the 7th International Teletrac Conference, pp. 318/1–318/4 (1973)
Reingold, O.: Undirected ST-connectivity in log-space. In: Proceedings of the 37th ACM Symposium on Theory of, Computing, pp. 376–385 (2005)
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)
Seidel, R.: On the all-pairs-shortest-path problem. In: Proceedings of the 24th ACM Symposium on Theory of, Computing, pp. 745–749 (1995)
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
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)