What can be approximated locally?: case study: dominating sets in planar graphs

ABSTRACT

Whether local algorithms can compute constant approximations of NP-hard problems is of both practical and theoretical interest. So far, no algorithms achieving this goal are known, as either the approximation ratio or the running time exceed O(1), or the nodes are provided with non-trivial additional information. In this paper, we present the first distributed algorithm approximating a minimum dominating set on a planar graph within a constant factor in constant time. Moreover, the nodes do not need any additional information.

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: Brent N. Clark , Charles J. Colbourn , David S. Johnson, Unit disk graphs, Discrete Mathematics, v.86 n.1-3, p.165-177, Dec. 14, 1990 [doi>10.1016/0012-365X(90)90358-O]
• 3: 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]
• 4: A. Czygrinow, M. Hanckowiak, and E. Szymanska. Distributed Approximation Algorithms for Planar Graphs. In Proceedings of the 6th Italian Conference on Algorithms and Complexity (CIAC), 2006.
• 5: P. Floréen, P. Kaski, T. Musto, and J. Suomela. Local Approximation Algorithms for Scheduling Problems in Sensor Networks. In Proceedings of the 3rd International Workshop on Algorithmic Aspects of Wireless Sensor Networks (Algosensors), 2007.
• 6: P. Floréen, P. Kaski, and J. Suomela. A distributed approximation scheme for sleep scheduling in sensor networks. In Proc. 4th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON, San Diego, CA, USA, June 2007), pages 152--161, Piscataway, NJ, USA, 2007. IEEE.
• 7: P. Fraigniaud, C. Gavoille, D. Ilcinkas, and A. Pelc. Distributed computing with advice: Information sensitivity of graph coloring. In 34th International Colloquium onAutomata, Languages and Programming (ICALP), pages 231--242, 2007.
• 8: Pierre Fraigniaud , David Ilcinkas , Andrzej Pelc, Oracle size: a new measure of difficulty for communication tasks, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146410]
• 9: Pierre Fraigniaud , Amos Korman , Emmanuelle Lebhar, Local MST computation with short advice, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248402]
• 10: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 11: 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]
• 12: Amos Israel , A. Itai, A fast and simple randomized parallel algorithm for maximal matching, Information Processing Letters, v.22 n.2, p.77-80, 1986 [doi>10.1016/0020-0190(86)90144-4]
• 13: Lujun Jia , Rajmohan Rajaraman , Torsten Suel, An efficient distributed algorithm for constructing small dominating sets, Distributed Computing, v.15 n.4, p.193-205, December 2002 [doi>10.1017/s00446-002-0078-0]
• 14: F. Kuhn, T. Moscibroda, T. Nieberg, and R. Wattenhofer. Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs. In Proc. 19th International Symposium on Distributed Computing (DISC), 2005.
• 15: 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]
• 16: 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]
• 17: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, The price of being near-sighted, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.980-989, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109666]
• 18: Fabian Kuhn , Roger Wattenhofer, Constant-time distributed dominating set approximation, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.25-32, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872040]
• 19: Nathan Linial, Locality in distributed graph algorithms, SIAM Journal on Computing, v.21 n.1, p.193-201, Feb. 1992 [doi>10.1137/0221015]
• 20: 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]
• 21: Moni Naor , Larry Stockmeyer, What Can Be Computed Locally?, SIAM Journal on Computing, v.24 n.6, p.1259-1277, Dec. 1995 [doi>10.1137/S0097539793254571]
• 22: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 23: J. Schneider and R. Wattenhofer. A Log-Star Distributed Maximal Independent Set Algorithm for Growth-Bounded Graphs. In 27th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, August 2008.
• 24: A. Wiese and E. Kranakis. Local PTAS for Independent Set and Vertex Cover in Location Aware Unit Disk Graphs. In Proceedings of the 4th IEEE/ACM International Conference on Distributed Computing in Sensor Systems (DCOSS), June 2008.

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: Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
approximation, distributed algorithms, dominating sets, local algorithms, planar graphs