research-article

Lower bounds for local approximation

Authors:

Jukka SuomelaAuthors Info & Claims

Journal of the ACM (JACM), Volume 60, Issue 5

Article No.: 39, Pages 1 - 23

https://doi.org/10.1145/2528405

Published: 28 October 2013 Publication History

Abstract

In the study of deterministic distributed algorithms, it is commonly assumed that each node has a unique O(log n)-bit identifier. We prove that for a general class of graph problems, local algorithms (constant-time distributed algorithms) do not need such identifiers: a port numbering and orientation is sufficient.

Our result holds for so-called simple PO-checkable graph optimisation problems; this includes many classical packing and covering problems such as vertex covers, edge covers, matchings, independent sets, dominating sets, and edge dominating sets. We focus on the case of bounded-degree graphs and show that if a local algorithm finds a constant-factor approximation of a simple PO-checkable graph problem with the help of unique identifiers, then the same approximation ratio can be achieved on anonymous networks.

As a corollary of our result, we derive a tight lower bound on the local approximability of the minimum edge dominating set problem. By prior work, there is a deterministic local algorithm that achieves the approximation factor of 4--1/⌊Δ/2⌋ in graphs of maximum degree Δ. This approximation ratio is known to be optimal in the port-numbering model—our main theorem implies that it is optimal also in the standard model in which each node has a unique identifier.

Our main technical tool is an algebraic construction of homogeneously ordered graphs: We say that a graph is (α,r)-homogeneous if its nodes are linearly ordered so that an α fraction of nodes have pairwise isomorphic radius-r neighbourhoods. We show that there exists a finite (α,r)-homogeneous 2k-regular graph of girth at least g for any α < 1 and any r, k, and g.

References

[1]

Angluin, D. 1980. Local and global properties in networks of processors. In Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC). ACM Press, New York, 82--93.

Digital Library

[2]

Angluin, D. and Gardiner, A. 1981. Finite common coverings of pairs of regular graphs. J. Combinatorial Theory, Series B 30, 2, 184--187.

[3]

Åsc strand, M., Floréen, P., Polishchuk, V., Rybicki, J., Suomela, J., and Uitto, J. 2009. A local 2-approximation algorithm for the vertex cover problem. In Proceedings of the 23rd International Symposium on Distributed Computing (DISC). Lecture Notes in Computer Science, vol. 5805, Springer, Berlin, 191--205.

Digital Library

[4]

Åsc strand, M., Polishchuk, V., Rybicki, J., Suomela, J., and Uitto, J. 2010. Local algorithms in (weakly) coloured graphs. Manuscript, arXiv:1002.0125 {cs.DC}.

[5]

Åsc strand, M. and Suomela, J. 2010. Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks. In Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM Press, New York, 294--302.

Digital Library

[6]

Attiya, H., Snir, M., and Warmuth, M. K. 1988. Computing on an anonymous ring. J. ACM 35, 4, 845--875.

Digital Library

[7]

Boldi, P., Shammah, S., Vigna, S., Codenotti, B., Gemmell, P., and Simon, J. 1996. Symmetry breaking in anonymous networks: characterizations. In Proceedings of the 4th Israel Symposium on the Theory of Computing and Systems (ISTCS). IEEE, 16--26.

[8]

Chlebík, M. and Chlebíková, J. 2006. Approximation hardness of edge dominating set problems. J. Combinat. Optimiz. 11, 3, 279--290.

[9]

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

Digital Library

[10]

Conder, M., Exoo, G., and Jajcay, R. 2010. On the limitations of the use of solvable groups in Cayley graph cage constructions. Euro. J. Combinat. 31, 1819--1828.

Digital Library

[11]

Conrad, P. 1959. Right-ordered groups. Michi. Math. J. 6, 267--275.

[12]

Czygrinow, A., Hańćkowiak, M., and Wawrzyniak, W. 2008. Fast distributed approximations in planar graphs. In Proceedings of the 22nd International Symposium on Distributed Computing (DISC). Lecture Notes in Computer Science, vol. 5218, Springer, Berlin, 78--92.

Digital Library

[13]

Fraigniaud, P., Halldorsson, M. M., and Korman, A. 2012. On the impact of identifiers on local decision. In Proceedings of the 16th International Conference on Principles of Distributed Systems (OPODIS). Lecture Notes in Computer Science, vol. 7702, Springer, Berlin, 224--238.

[14]

Gamburd, A., Hoory, S., Shahshahani, M., Shalev, A., and Virág, B. 2009. On the girth of random Cayley graphs. Rand. Struct. Algor. 35, 1, 100--117.

Digital Library

[15]

Göös, M., Hirvonen, J., and Suomela, J. 2012. Lower bounds for local approximation. In Proceedings of the 31st Annual ACM Symposium on Principles of Distributed Computing (PODC). ACM, New York, 175--184.

Digital Library

[16]

Graham, R. L., Rothschild, B. L., and Spencer, J. H. 1980. Ramsey Theory. Wiley, New York.

[17]

Gromov, M. 1981. Groups of polynomial growth and expanding maps. Publications Mathématiques de L'IHÉS 53, 53--78.

[18]

Hasemann, H., Hirvonen, J., Rybicki, J., and Suomela, J. 2012. Deterministic local algorithms, unique identifiers, and fractional graph colouring. In Proceedings of the 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO). Lecture Notes in Computer Science, vol. 7355, Springer, Berlin, 48--60.

Digital Library

[19]

Hella, L., Järvisalo, M., Kuusisto, A., Laurinharju, J., Lempiäinen, T., Luosto, K., Suomela, J., and Virtema, J. 2012. Weak models of distributed computing, with connections to modal logic. In Proceedings of the 31st Annual ACM Symposium on Principles of Distributed Computing (PODC). ACM, New York, 185--194.

Digital Library

[20]

Hirvonen, J. and Suomela, J. 2012. Distributed maximal matching: Greedy is optimal. In Proceedings of the 31st Annual ACM Symposium on Principles of Distributed Computing (PODC). ACM, New York, 165--174.

Digital Library

[21]

Hoepman, J.-H., Kutten, S., and Lotker, Z. 2006. Efficient distributed weighted matchings on trees. In Proceedings of the 13th International Colloquium on Structural Information and Communication Complexity (SIROCCO). Lecture Notes in Computer Science, vol. 4056, Springer, Berlin, 115--129.

Digital Library

[22]

Kuhn, F. 2005. The price of locality: Exploring the complexity of distributed coordination primitives. Ph.D. thesis, ETH Zurich.

[23]

Kuhn, F., Moscibroda, T., and Wattenhofer, R. 2004. What cannot be computed locally&excl; In Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC). ACM, New York, 300--309.

Digital Library

[24]

Kuhn, F., Moscibroda, T., and Wattenhofer, R. 2006a. Fault-tolerant clustering in ad hoc and sensor networks. In Proceedings of the 26th IEEE International Conference on Distributed Computing Systems (ICDCS). IEEE Computer Society Press, Los Alamitos, CA.

Digital Library

[25]

Kuhn, F., Moscibroda, T., and Wattenhofer, R. 2006b. The price of being near-sighted. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, New York, 980--989.

Digital Library

[26]

Kuhn, F., Moscibroda, T., and Wattenhofer, R. 2010. Local computation: Lower and upper bounds. Manuscript, arXiv:1011.5470 {cs.DC}.

[27]

Kuhn, F. and Wattenhofer, R. 2005. Constant-time distributed dominating set approximation. Distrib. Comput. 17, 4, 303--310.

Digital Library

[28]

Lenzen, C. 2011. Synchronization and symmetry breaking in distributed systems. Ph.D. thesis, ETH Zurich.

[29]

Lenzen, C. and Wattenhofer, R. 2008. Leveraging Linial's locality limit. In Proceedings of the 22nd International Symposium on Distributed Computing (DISC). Lecture Notes in Computer Science, vol. 5218, Springer, Berlin, 394--407.

Digital Library

[30]

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

Digital Library

[31]

Mayer, A., Naor, M., and Stockmeyer, L. 1995. Local computations on static and dynamic graphs. In Proceedings of the 3rd Israel Symposium on the Theory of Computing and Systems (ISTCS). IEEE, 268--278.

Digital Library

[32]

Naor, M. 1991. A lower bound on probabilistic algorithms for distributive ring coloring. SIAM J. Disc. Math. 4, 3, 409--412.

[33]

Naor, M. and Stockmeyer, L. 1995. What can be computed locally&quest; SIAM J. Comput. 24, 6, 1259--1277.

Digital Library

[34]

Nguyen, H. N. and Onak, K. 2008. Constant-time approximation algorithms via local improvements. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 327--336.

Digital Library

[35]

Peleg, D. 2000. Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics and Applications, SIAM, Philadelphia.

Digital Library

[36]

Rotman, J. J. 1995. An Introduction to the Theory of Groups. Graduate Texts in Mathematics Series, vol. 148, Springer, New York.

[37]

Suomela, J. 2010. Distributed algorithms for edge dominating sets. In Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing (PODC). ACM, New York, 365--374.

Digital Library

[38]

Suomela, J. 2013a. A bibliography of local algorithms. http://www.cs.helsinki.fi/local-survey.

[39]

Suomela, J. 2013b. Survey of local algorithms. ACM Comput. Surv. 45, 2, 24:1--40.

Digital Library

[40]

Wattenhofer, M. and Wattenhofer, R. 2004. Distributed weighted matching. In Proceedings of the 18th International Symposium on Distributed Computing (DISC). Lecture Notes in Computer Science, vol. 3274, Springer, Berlin, 335--348.

[41]

Yamashita, M. and Kameda, T. 1996. Computing on anonymous networks: Part I—Characterizing the solvable cases. IEEE Trans. Paral. Distrib. Syst. 7, 1, 69--89.

Digital Library

[42]

Yamashita, M. and Kameda, T. 1999. Leader election problem on networks in which processor identity numbers are not distinct. IEEE Trans. Paral. Distrib. Syst. 10, 9, 878--887.

Digital Library

[43]

Yannakakis, M. and Gavril, F. 1980. Edge dominating sets in graphs. SIAM J. Appl. Math. 38, 3, 364--372.

Digital Library

Cited By

Dahal SSuomela J(2024)Distributed half-integral matching and beyondTheoretical Computer Science10.1016/j.tcs.2023.114278982:COnline publication date: 8-Jan-2024
https://dl.acm.org/doi/10.1016/j.tcs.2023.114278
Lenzen CWenning S(2024)Tight Bounds for Constant-Round Domination on Graphs of High Girth and Low ExpansionStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-74498-3_20(277-291)Online publication date: 20-Oct-2024
https://doi.org/10.1007/978-3-031-74498-3_20
Chang YLi ZOshman RNolin AHalldorsson MBalliu A(2023)The Complexity of Distributed Approximation of Packing and Covering Integer Linear ProgramsProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594562(32-43)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594562
Show More Cited By

Index Terms

Lower bounds for local approximation

Recommendations

Lower bounds for local approximation
PODC '12: Proceedings of the 2012 ACM symposium on Principles of distributed computing

In the study of deterministic distributed algorithms it is commonly assumed that each node has a unique O(log n)-bit identifier. We prove that for a general class of graph problems, local algorithms (constant-time distributed algorithms) do not need ...
Approximating edge dominating set in dense graphs

We study the approximation complexity of the Minimum Edge Dominating Set problem in everywhere @e-dense and average @e@?-dense graphs. More precisely, we consider the computational complexity of approximating a generalization of the Minimum Edge ...
Approximation algorithms for clique transversals on some graph classes

Given a graph G = ( V , E ) a clique is a maximal subset of pairwise adjacent vertices of V of size at least 2. A clique transversal is a subset of vertices that intersects the vertex set of each clique of G. Finding a minimum-cardinality clique ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 60, Issue 5

October 2013

245 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/2528384

Issue’s Table of Contents

Copyright © 2013 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 the author(s) 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].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 October 2013

Accepted: 01 August 2013

Revised: 01 June 2013

Received: 01 November 2012

Published in JACM Volume 60, Issue 5

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
397
Total Downloads

Downloads (Last 12 months)16
Downloads (Last 6 weeks)2

Reflects downloads up to 14 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Dahal SSuomela J(2024)Distributed half-integral matching and beyondTheoretical Computer Science10.1016/j.tcs.2023.114278982:COnline publication date: 8-Jan-2024
https://dl.acm.org/doi/10.1016/j.tcs.2023.114278
Lenzen CWenning S(2024)Tight Bounds for Constant-Round Domination on Graphs of High Girth and Low ExpansionStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-74498-3_20(277-291)Online publication date: 20-Oct-2024
https://doi.org/10.1007/978-3-031-74498-3_20
Chang YLi ZOshman RNolin AHalldorsson MBalliu A(2023)The Complexity of Distributed Approximation of Packing and Covering Integer Linear ProgramsProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594562(32-43)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594562
Dahal SSuomela J(2023)Distributed Half-Integral Matching and BeyondStructural Information and Communication Complexity10.1007/978-3-031-32733-9_15(339-356)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-32733-9_15
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
Bamas ÉEsperet L(2020)Local approximation of the Maximum Cut in regular graphsTheoretical Computer Science10.1016/j.tcs.2020.03.008Online publication date: Mar-2020
https://doi.org/10.1016/j.tcs.2020.03.008
Bamas ÉEsperet L(2019)Local Approximation of the Maximum Cut in Regular GraphsGraph-Theoretic Concepts in Computer Science10.1007/978-3-030-30786-8_6(66-78)Online publication date: 19-Jun-2019
https://dl.acm.org/doi/10.1007/978-3-030-30786-8_6
Fraigniaud PHirvonen JSuomela J(2018)Node labels in local decisionTheoretical Computer Science10.1016/j.tcs.2017.01.011751(61-73)Online publication date: Dec-2018
https://doi.org/10.1016/j.tcs.2017.01.011
Wawrzyniak W(2018)A local approximation algorithm for minimum dominating set problem in anonymous planar networksDistributed Computing10.1007/s00446-015-0247-628:5(321-331)Online publication date: 26-Dec-2018
https://dl.acm.org/doi/10.1007/s00446-015-0247-6
Göös MHirvonen JSuomela J(2018)Linear-in-$$\varDelta $$Δ lower bounds in the LOCAL modelDistributed Computing10.1007/s00446-015-0245-830:5(325-338)Online publication date: 26-Dec-2018
https://dl.acm.org/doi/10.1007/s00446-015-0245-8
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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents