A local constant factor MDS approximation for bounded genus graphs

DOI10.1145/2933057.2933084MaRDI QIDQ5361940zbMATH OpenOpenAlexFDO

Authors Saeed Akhoondian Amiri, Stefan Schmid, Sebastian Siebertz

Publication date 29 September 2017

Published in Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.02991

zbMATH Keywords

approximation algorithmconstant-factor approximationdistributed systemfirst order definablegraph theorygraphs of bounded genuslocal modellocally embeddable graphslogicminimum dominating setplanar graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Abstract: The Minimum Dominating Set (MDS) problem is not only one of the most fundamental problems in distributed computing, it is also one of the most challenging ones. While it is well-known that minimum dominating sets cannot be approximated locally on general graphs, over the last years, several breakthroughs have been made on computing local approximations on sparse graphs. This paper presents a deterministic and local constant factor approximation for minimum dominating sets on bounded genus graphs, a very large family of sparse graphs. Our main technical contribution is a new analysis of a slightly modified, first-order definable variant of an existing algorithm by Lenzen et al. Interestingly, unlike existing proofs for planar graphs, our analysis does not rely on any topological arguments. We believe that our techniques can be useful for the study of local problems on sparse graphs beyond the scope of this paper.

Recommendations

• Distributed Dominating Set Approximations beyond Planar Graphs
• Distributed \(\mathcal{CONGEST}_{B C}\) constant approximation of MDS in bounded genus graphs
• Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs
• A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
• A local approximation algorithm for minimum dominating set problem in anonymous planar networks

Cited in

(17)

• Distributed \(\mathcal{CONGEST}_{B C}\) constant approximation of MDS in bounded genus graphs
• Local certification of graphs with bounded genus
• Constant round distributed domination on graph classes with bounded expansion
• Distributed distance domination in graphs with no \(K_{2,t}\)-minor
• Distributed approximation algorithms for k-dominating set in graphs of bounded genus and linklessly embeddable graphs
• A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
• Property testing of planarity in the \textsf{CONGEST} model
• Distributed Dominating Set Approximations beyond Planar Graphs
• Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs
• Distributed Approximation Algorithms for the Minimum Dominating Set in K_h-Minor-Free Graphs
• Distributed distance-r covering problems on sparse high-girth graphs
• The energy complexity of diameter and minimum cut computation in bounded-genus networks
• The energy complexity of diameter and minimum cut computation in bounded-genus networks
• Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
• Distributed domination on sparse graph classes
• Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
• Efficient distributed decomposition and routing algorithms in minor-free networks and their applications

This page was built for publication: A local constant factor MDS approximation for bounded genus graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361940)