Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition

ABSTRACT

We study the distributed maximal independent set (henceforth, MIS) problem on sparse graphs. Currently, there are known algorithms with a sublogarithmic running time for this problem on oriented trees and graphs of bounded degrees. We devise the first sublogarithmic algorithm for computing MIS on graphs of bounded arboricity. This is a large family of graphs that includes graphs of bounded degree, planar graphs, graphs of bounded genus, graphs of bounded treewidth, graphs that exclude a fixed minor, and many other graphs. We also devise efficient algorithms for coloring graphs from these families. These results are achieved by the following technique that may be of independent interest. Our algorithm starts with computing a certain graph-theoretic structure, called Nash-Williams forests-decomposition. Then this structure is used to compute the MIS or coloring. Our results demonstrate that this methodology is very powerful. Finally, we show nearly-tight lower bounds on the running time of any distributed algorithm for computing a forests-decomposition.

REFERENCES

• 1: Noga Alon , László Babai , Alon Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, Journal of Algorithms, v.7 n.4, p.567-583, Dec. 1986 [doi>10.1016/0196-6774(86)90019-2]
• 2: Srinivasa R. Arikati , Anil Maheshwari , Christos D. Zaroliagis, Efficient computation of implicit representations of sparse graphs, Discrete Applied Mathematics, v.78 n.1-3, p.1-16, Oct. 21, 1997 [doi>10.1016/S0166-218X(97)00007-3]
• 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: Béla Bollobas, Extremal Graph Theory, Dover Publications, Incorporated, 2004
• 5: 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]
• 6: N. Deo and B. Litow. A structural approach to graph compression. In Proc. of the MFCS Workshop on Communications, pages 91--100, 1998.
• 7: Vida Dujmovic , David R. Wood, Graph Treewidth and Geometric Thickness Parameters, Discrete & Computational Geometry, v.37 n.4, p.641-670, May 2007 [doi>10.1007/s00454-007-1318-7]
• 8: P. Erd\Hos, 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: Beat Gfeller , Elias Vicari, A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281111]
• 10: A. Goldberg, and S. Plotkin. Efficient parallel algorithms for (Δ 1) - coloring and maximal independent set problem. In Proc. 19th ACM Symposium on Theory of Computing, pages 315--324, 1987.
• 11: 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]
• 12: K. Kothapalli, C. Scheideler, M. Onus, and C. Schindelhauer. Distributed coloring in O($\sqrtlog n$) bit rounds. In Proc. of the 20th International Parallel and Distributed Processing Symposium, 2006.
• 13: F. Kuhn, T. Moscibroda, T. Nieberg, and R. Wattenhofer. Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs.In 19th International Symposium on Distributed Computing, 2005.
• 14: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, What cannot be computed locally!, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011811]
• 15: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, On the locality of bounded growth, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073826]
• 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: 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]
• 19: C. Nash-Williams. Decompositions of finite graphs into forests. J. London Math, 39:12, 1964.
• 20: 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]
• 21: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 22: 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]
• 23: Gurdip Singh, Efficient leader election using sense of direction, Distributed Computing, v.10 n.3, p.159-165, April 1997 [doi>10.1007/s004460050033]
• 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]

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

General Terms:
Algorithms

Keywords:
arboricity, coloring, forests decomposition, mis