research-article

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

Authors:

Christoph Lenzen,

Yvonne Anne Oswald,

Roger WattenhoferAuthors Info & Claims

SPAA '08: Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures

Pages 46 - 54

https://doi.org/10.1145/1378533.1378540

Published: 14 June 2008 Publication History

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]

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

Digital Library

[2]

B. N. Clark, C. J. Colbourn, and D. S. Johnson. Unit disk graphs. Discrete Math., 86(1-3):165--177, 1990.

Digital Library

[3]

R. Cole and U. Vishkin. Deterministic Coin Tossing with Applications to Optimal Parallel List Ranking. Information and Control, 70(1):32--53, 1986.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[8]

P. Fraigniaud, D. Ilcinkas, and A. Pelc. Oracle size: a new measure of difficulty for communication tasks. In Proceedings of the 25th annual ACM symposium on Principles of distributed computing (PODC), pages 179--187, 2006.

Digital Library

[9]

P. Fraigniaud, A. Korman, and E. Lebhar. Local mst computation with short advice. In Proceedings of the 19th annual ACM symposium on Parallel algorithms and architectures (SPAA), pages 154--160, 2007.

Digital Library

[10]

M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, 1979.

Digital Library

[11]

B. Gfeller and E. Vicari. A Randomized Distributed Algorithm for the Maximal Independent Set Problem in Growth-Bounded Graphs. In Proc. 26th annual ACM symposium on Principles of distributed computing (PODC), 2007.

Digital Library

[12]

A. Israel and A. Itai. A fast and simple randomized parallel algorithm for maximal matching. Information Processing Letters, 22(2):77--80, 1986.

Digital Library

[13]

L. Jia, R. Rajaraman, and T. Suel. An Efficient Distributed Algorithm for Constructing Small Dominating Sets. Distributed Computing, 15(4):193--205, 2002.

Digital Library

[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.

Digital Library

[15]

F. Kuhn, T. Moscibroda, and R. Wattenhofer. What Cannot Be Computed Locally! In Proc. 23rd annual ACM symposium on Principles of distributed computing (PODC), 2004.

Digital Library

[16]

F. Kuhn, T. Moscibroda, and R. Wattenhofer. On the Locality of Bounded Growth. In Proc. 24th ACM Symposium on the Principles of Distributed Computing (PODC), 2005.

Digital Library

[17]

F. Kuhn, T. Moscibroda, and R. Wattenhofer. The Price of Being Near-Sighted. In Proc. 17th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006.

Digital Library

[18]

F. Kuhn and R. Wattenhofer. Constant-Time Distributed Dominating Set Approximation. In Proc. 22nd ACM Symposium on the Principles of Distributed Computing (PODC), 2003.

Digital Library

[19]

N. Linial. Locality in Distributed Graph Algorithms. SIAM Journal on Computing, 21(1):193--201, 1992.

Digital Library

[20]

M. Luby. A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM Journal on Computing, 15(4):1036--1055, 1986.

Digital Library

[21]

M. Naor and L. Stockmeyer. What Can Be Computed Locally? SIAM Journal on Computing, 24(6):1259--1277, 1995.

Digital Library

[22]

D. Peleg. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000.

Digital Library

[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.

Digital Library

[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.

Digital Library

Cited By

Feuilloley LFraigniaud PMontealegre PRapaport IRémila ÉTodinca I(2023)Local certification of graphs with bounded genusDiscrete Applied Mathematics10.1016/j.dam.2022.10.004325(9-36)Online publication date: Jan-2023
https://doi.org/10.1016/j.dam.2022.10.004
Dory MGhaffari MIlchi S(2023)Near-optimal distributed dominating set in bounded arboricity graphsDistributed Computing10.1007/s00446-023-00447-z37:4(387-398)Online publication date: 15-May-2023
https://doi.org/10.1007/s00446-023-00447-z
Dory MGhaffari MIlchi SMilani AWoelfel P(2022)Near-Optimal Distributed Dominating Set in Bounded Arboricity GraphsProceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538437(292-300)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.1145/3519270.3538437
Show More Cited By

Index Terms

What can be approximated locally?: case study: dominating sets in planar graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Complexity and approximation of the Constrained Forest problem

Given an undirected graph on n vertices with weights on its edges, Min WCF (p) consists of computing a covering forest of minimum weight such that each of its tree components contains at least p vertices. It has been proved that Min WCF (p) is NP-hard ...
Total domination in planar graphs of diameter two

MacGillivary and Seyffarth [G. MacGillivray, K. Seyffarth, Domination numbers of planar graphs, J. Graph Theory 22 (1996) 213-229] proved that planar graphs of diameter two have domination number at most three. Goddard and Henning [W. Goddard, M.A. ...
Planar graphs without 4- and 5-cycles are acyclically 4-choosable

Let G=(V,E) be a graph. A proper vertex coloring of G is acyclic if G contains no bicolored cycle. Namely, every cycle of G must be colored with at least three colors. G is acyclically L-list colorable if for a given list assignment L={L(v):v@?V}, there ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '08: Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures

June 2008

380 pages

ISBN:9781595939739

DOI:10.1145/1378533

General Chair:
Friedhelm Meyer auf der Heide
University of Paderborn, Germany
,
Program Chair:
Nir Shavit
Tel-Aviv University, Israel, and Sun Labs, USA

Copyright © 2008 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SPAA08

Sponsor:

SPAA08: 20th ACM Symposium on Parallelism in Algorithms and Architectures

June 14 - 16, 2008

Munich, Germany

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
326
Total Downloads

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

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Feuilloley LFraigniaud PMontealegre PRapaport IRémila ÉTodinca I(2023)Local certification of graphs with bounded genusDiscrete Applied Mathematics10.1016/j.dam.2022.10.004325(9-36)Online publication date: Jan-2023
https://doi.org/10.1016/j.dam.2022.10.004
Dory MGhaffari MIlchi S(2023)Near-optimal distributed dominating set in bounded arboricity graphsDistributed Computing10.1007/s00446-023-00447-z37:4(387-398)Online publication date: 15-May-2023
https://doi.org/10.1007/s00446-023-00447-z
Dory MGhaffari MIlchi SMilani AWoelfel P(2022)Near-Optimal Distributed Dominating Set in Bounded Arboricity GraphsProceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538437(292-300)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.1145/3519270.3538437
Barenboim LOren G(2022)Distributed backup placementDistributed Computing10.1007/s00446-022-00423-z35:5(455-473)Online publication date: 24-Mar-2022
https://doi.org/10.1007/s00446-022-00423-z
Feuilloley LFraigniaud P(2021)Randomized Local Network Computing: Derandomization Beyond Locally Checkable LabelingsACM Transactions on Parallel Computing10.1145/34706408:4(1-25)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3470640
Feuilloley LFraigniaud PMontealegre PRapaport IRémila ÉTodinca I(2021)Compact Distributed Certification of Planar GraphsAlgorithmica10.1007/s00453-021-00823-wOnline publication date: 6-May-2021
https://doi.org/10.1007/s00453-021-00823-w
Feuilloley LFraigniaud PMontealegre PRapaport IRémila ÉTodinca IEmek YCachin C(2020)Compact Distributed Certification of Planar GraphsProceedings of the 39th Symposium on Principles of Distributed Computing10.1145/3382734.3404505(319-328)Online publication date: 31-Jul-2020
https://dl.acm.org/doi/10.1145/3382734.3404505
Feuilloley LFraigniaud PHirvonen J(2020)A hierarchy of local decisionTheoretical Computer Science10.1016/j.tcs.2020.12.017Online publication date: Dec-2020
https://doi.org/10.1016/j.tcs.2020.12.017
Kuhn FMoscibroda TWattenhofer R(2016)Local ComputationJournal of the ACM10.1145/274201263:2(1-44)Online publication date: 31-Mar-2016
https://dl.acm.org/doi/10.1145/2742012
Mahmood AMaroosi AMuniyandi R(2016)Membrane Computing to Enhance Time Efficiency of Minimum Dominating SetMathematics in Computer Science10.1007/s11786-016-0261-510:2(249-261)Online publication date: 24-Mar-2016
https://doi.org/10.1007/s11786-016-0261-5
Show More Cited By

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents