More Web Proxy on the site http://driver.im/

research-article

Distributed Domination on Graph Classes of Bounded Expansion

Authors:

Saeed Akhoondian Amiri,

Patrice Ossona de Mendez,

Roman Rabinovich,

Sebastian SiebertzAuthors Info & Claims

SPAA '18: Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures

Pages 143 - 151

https://doi.org/10.1145/3210377.3210383

Published: 11 July 2018 Publication History

Abstract

\noindent We provide a new constant factor approximation algorithm for the (connected) \mboxdistance- r dominating set problem on graph classes of bounded expansion. Classes of bounded expansion include many familiar classes of sparse graphs such as planar graphs and graphs with excluded (topological) minors, and notably, these classes form the most general subgraph closed classes of graphs for which a sequential constant factor approximation algorithm for the distance- r dominating set problem is currently known. Our algorithm can be implemented in the \congestbc model of distributed computing and uses $Øof(r^2 łog n)$ communication rounds. % Our techniques, which may be of independent interest, are based on a distributed computation of sparse neighborhood covers of small radius on bounded expansion classes. We show how to compute an r -neighborhood cover of radius~$2r$ and overlap $f(r)$ on every class of bounded expansion in $Øof(r^2łog n)$ communication rounds for some function~ f .% in the \congestbc model. % Finally, we show how to use the greater power of the łocal model to turn any distance- r dominating set into a constantly larger connected distance- r dominating set in $3r+1$ rounds on any class of bounded expansion. Combining this algorithm, e.g., with the constant factor approximation algorithm for dominating sets on planar graphs of Lenzen et al.\ gives a constant factor approximation algorithm for connected dominating sets on planar graphs in a constant number of rounds in the łocal model, where the approximation ratio is only $6$ times larger than that of Lenzen et al.'s algorithm.

References

[1]

Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, and Kunal Talwar. 2014. Cops, robbers, and threatening skeletons: padded decomposition for minorfree graphs. In Symposium on Theory of Computing, STOC 2014. 79--88.

Digital Library

[2]

Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. 2005. Compact routing for graphs excluding a fixed minor. In International Symposium on Distributed Computing. Springer, 442--456.

Digital Library

[3]

Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, and Udi Wieder. 2007. Strongdiameter decompositions of minor free graphs. In Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures. ACM, 16--24.

Digital Library

[4]

Noga Alon, Dana Moshkovitz, and Shmuel Safra. 2006. Algorithmic construction of sets for k-restrictions. ACM Transactions on Algorithms (TALG) 2, 2 (2006), 153--177.

Digital Library

[5]

Saeed Akhoondian Amiri, Stefan Schmid, and Sebastian Siebertz. 2016. A Local Constant Factor MDS Approximation for Bounded Genus Graphs. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016. 227--233.

Digital Library

[6]

Sanjeev Arora and Madhu Sudan. 2003. Improved low-degree testing and its applications. Combinatorica 23, 3 (2003), 365--426.

[7]

Baruch Awerbuch and David Peleg. 1990. Locality-sensitive resource allocation. Citeseer.

[8]

Baruch Awerbuch and David Peleg. 1990. Network synchronization with polylogarithmic overhead. In Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on. IEEE, 514--522.

Digital Library

[9]

Baruch Awerbuch and David Peleg. 1990. Sparse partitions. In Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on. IEEE, 503--513.

Digital Library

[10]

Nikhil Bansal and Seeun William Umboh. 2017. Tight approximation bounds for dominating set on graphs of bounded arboricity. Inform. Process. Lett. 122 (2017), 21--24.

[11]

Leonid Barenboim and Michael Elkin. 2010. Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition. Distributed Computing 22, 5--6 (2010), 363--379.

Digital Library

[12]

M. Bellare, S. Goldwasser, C. Lund, and A. Russell. 1993. Efficient multi-prover interactive proofs with applications to approximation problems. In Proc. 25th ACM Symp. on Theory of Computing, Vol. 113. 131.

Digital Library

[13]

Costas Busch, Ryan LaFortune, and Srikanta Tirthapura. 2007. Improved sparse covers for graphs excluding a fixed minor. In Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing. ACM, 61--70.

Digital Library

[14]

Fan Chung and Linyuan Lu. 2002. Connected components in random graphs with given expected degree sequences. Annals of combinatorics 6, 2 (2002), 125--145.

[15]

Vasek Chvatal. 1979. A greedy heuristic for the set-covering problem. Mathematics of operations research 4, 3 (1979), 233--235.

Digital Library

[16]

Andrzej Czygrinow, Michal Hańćkowiak, and Wojciech Wawrzyniak. 2008. Fast distributed approximations in planar graphs. In International Symposium on Distributed Computing. Springer, 78--92.

Digital Library

[17]

Bevan Das and Vaduvur Bharghavan. 1997. Routing in ad-hoc networks using minimum connected dominating sets. In Communications, 1997. ICC'97 Montreal, Towards the Knowledge Millennium. 1997 IEEE International Conference on, Vol. 1. IEEE, 376--380.

[18]

Bevan Das, Raghupathy Sivakumar, and Vaduvur Bharghavan. 1997. Routing in ad hoc networks using a spine. In Computer Communications and Networks, 1997. Proceedings., Sixth International Conference on. IEEE, 34--39.

Digital Library

[19]

Erik D Demaine, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, Somnath Sikdar, and Blair D Sullivan. 2014. Structural sparsity of complex networks: Bounded expansion in random models and real-world graphs. arXiv preprint arXiv:1406.2587 (2014).

[20]

Irit Dinur and David Steurer. 2014. Analytical approach to parallel repetition. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing. ACM, 624--633.

Digital Library

[21]

Zdeněk DvoƳák. 2013. Constant-factor approximation of the domination number in sparse graphs. European Journal of Combinatorics 34, 5 (2013), 833--840.

Digital Library

[22]

Uriel Feige. 1998. A threshold of ln n for approximating set cover. Journal of the ACM (JACM) 45, 4 (1998), 634--652.

Digital Library

[23]

Michael R. Garey and David S. Johnson. 1979. Computers and intractability: a guide to the theory of NP-completeness. WH Free. Co., San Fr (1979).

Digital Library

[24]

Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus. 2017. On the complexity of local distributed graph problems. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017. 784--797.

Digital Library

[25]

Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, and Konstantinos Stavropoulos. 2015. Colouring and Covering Nowhere Dense Graphs. In Graph-Theoretic Concepts in Computer Science - 41st International Workshop, WG 2015. 325--338.

Digital Library

[26]

Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. 2014. Deciding firstorder properties of nowhere dense graphs. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing. ACM, 89--98.

Digital Library

[27]

Sariel Har-Peled and Kent Quanrud. 2015. Approximation algorithms for polynomial-expansion and low-density graphs. In Algorithms-ESA 2015. Springer, 717--728.

[28]

Teresa W Haynes, Stephen Hedetniemi, and Peter Slater. 1998. Fundamentals of domination in graphs. CRC Press.

[29]

Miikka Hilke, Christoph Lenzen, and Jukka Suomela. 2014. Brief announcement: Local approximability of minimum dominating set on planar graphs. In Proceedings of the 2014 ACM symposium on Principles of distributed computing. ACM, 344--346.

Digital Library

[30]

Viggo Kann. 1992. On the approximability of NP-complete optimization problems. Ph.D. Dissertation. Royal Institute of Technology Stockholm.

[31]

Richard M Karp. 1972. Reducibility among combinatorial problems. In Complexity of computer computations. Springer, 85--103.

[32]

Hal A. Kierstead and Daqing Yang. 2003. Orderings on graphs and game coloring number. Order 20, 3 (2003), 255--264.

[33]

Stephan Kreutzer, Michał Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. 2016. The Generalised Colouring Numbers on Classes of Bounded Expansion. In 41st International Symposium on Mathematical Foundations of Computer Science, MFCS. 85:1--85:13.

[34]

Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. 2016. Local computation: Lower and upper bounds. Journal of the ACM (JACM) 63, 2 (2016), 17.

Digital Library

[35]

Shay Kutten and David Peleg. 1995. Fast distributed construction of k-dominating sets and applications. In Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing. ACM, 238--251.

Digital Library

[36]

Christoph Lenzen, Yvonne-Anne Pignolet, and Roger Wattenhofer. 2013. Distributed minimum dominating set approximations in restricted families of graphs. Distributed computing 26, 2 (2013), 119--137.

[37]

Christoph Lenzen and Roger Wattenhofer. 2008. Leveraging Linial's locality limit. In International Symposium on Distributed Computing. Springer, 394--407.

Digital Library

[38]

Christoph Lenzen and Roger Wattenhofer. 2010. Minimum dominating set approximation in graphs of bounded arboricity. In International Symposium on Distributed Computing. Springer, 510--524.

Digital Library

[39]

László Lovász. 1975. On the ratio of optimal integral and fractional covers. Discrete mathematics 13, 4 (1975), 383--390.

Digital Library

[40]

Carsten Lund and Mihalis Yannakakis. 1994. On the hardness of approximating minimization problems. Journal of the ACM (JACM) 41, 5 (1994), 960--981.

Digital Library

[41]

Michael Molloy and Bruce Reed. 1995. A critical point for random graphs with a given degree sequence. Random structures & algorithms 6, 2--3 (1995), 161--180.

Digital Library

[42]

Jaroslav Nešetřil and Patrice Ossona de Mendez. 2008. Grad and classes with bounded expansion I. Decompositions. European Journal of Combinatorics 29, 3 (2008), 760--776.

Digital Library

[43]

Jaroslav Nešetřil and Patrice Ossona de Mendez. 2008. Grad and classes with bounded expansion II. Algorithmic aspects. European Journal of Combinatorics 29, 3 (2008), 777--791.

Digital Library

[44]

Jaroslav Nešetřil and Patrice Ossona de Mendez. 2008. Grad and classes with bounded expansion III. Restricted graph homomorphism dualities. European Journal of Combinatorics 29, 4 (2008), 1012--1024.

Digital Library

[45]

Jaroslav Nešetřil and Patrice Ossona de Mendez. 2012. Sparsity. Springer.

[46]

Jaroslav Nešetřil and Patrice Ossona de Mendez. 2016. A distributed low treedepth decomposition algorithm for bounded expansion classes. Distributed Computing 29, 1 (2016), 39--49.

Digital Library

[47]

Jaroslav Nešetřil, Patrice Ossona de Mendez, and David R. Wood. 2012. Characterizations and Examples of Graph Classes with Bounded Expansion. European Journal of Combinatorics 33, 3 (2012), 350--373.

Digital Library

[48]

David Peleg. 2000. Distributed computing: a locality sensitive approach. SIAM Monographs on discrete mathematics and applications 5 (2000).

Digital Library

[49]

Lucia D. Penso and Valmir C. Barbosa. 2004. A distributed algorithm to find k-dominating sets. Discrete Applied Mathematics 141, 1 (2004), 243--253.

Digital Library

[50]

Ran Raz and Shmuel Safra. 1997. A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. ACM, 475--484.

Digital Library

[51]

R. Sivakumar, B. Das, and V. Bharghavan. 1998. An improved spine-based infrastructure for routing in ad hoc networks. In IEEE Symposium on Computers and Communications, Vol. 98.

[52]

Ivan Stojmenovic, Mahtab Seddigh, and Jovisa Zunic. 2002. Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks. IEEE Transactions on parallel and distributed systems 13, 1 (2002), 14--25.

Digital Library

[53]

Mikkel Thorup and Uri Zwick. 2005. Approximate distance oracles. Journal of the ACM (JACM) 52, 1 (2005), 1--24.

Digital Library

[54]

Volker Turau and Sven Köhler. 2015. A Distributed Algorithm for Minimum Distance-k Domination in Trees. Journal of Graph Algorithms and Applications 19, 1 (2015), 223--242.

[55]

Jan van den Heuvel, Patrice Ossona de Mendez, Daniel Quiroz, Roman Rabinovich, and Sebastian Siebertz. 2017. On the generalised colouring numbers of graphs that exclude a fixed minor. Eur. J. Comb. 66 (2017), 129--144.

[56]

Fu-Hsing Wang, Jou-Ming Chang, Yue-Li Wang, and Sun-Jen Huang. 2003. Distributed algorithms for finding the unique minimum distance dominating set in directed split-stars. J. Parallel and Distrib. Comput. 63, 4 (2003), 481--487.

Digital Library

[57]

Wojciech Wawrzyniak. 2014. A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs. Inform. Process. Lett. 114, 3 (2014), 94--98.

Digital Library

[58]

Jie Wu and Hailan Li. 1999. On calculating connected dominating set for efficient routing in ad hoc wireless networks. In Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications. ACM, 7--14.

Digital Library

[59]

Xuding Zhu. 2009. Colouring graphs with bounded generalized colouring number. Discrete Mathematics 309, 18 (2009), 5562--5568.

Digital Library

Cited By

Heydt OKublenz SOssona de Mendez PSiebertz SVigny A(2025)Distributed domination on sparse graph classesEuropean Journal of Combinatorics10.1016/j.ejc.2023.103773123(103773)Online publication date: Jan-2025
https://doi.org/10.1016/j.ejc.2023.103773
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
Show More Cited By

Index Terms

Distributed Domination on Graph Classes of Bounded Expansion
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Small graph classes and bounded expansion

A class of simple undirected graphs is small if it contains at most n!@a^n labeled graphs with n vertices, for some constant @a. We prove that for any constants c,@e>0, the class of graphs with expansion bounded by the function f(r)=c^r^^^1^^^/^^^3^^^-^^...
Domination in a graph with a 2-factor

Let γ(G) be the domination number of a graph G. Reed [6] proved that every graph G of minimum degree at least three satisfies γ(G) ≤ (3-8)|G|, and conjectured that a better upper bound can be obtained for cubic graphs. In this paper, we prove that a 2-...
Hereditary Domination in Graphs: Characterization with Forbidden Induced Subgraphs

The leaf graph of a connected graph is obtained by joining a new vertex of degree one to each noncutting vertex. We prove that if a connected graph $G$ is not dominated by any of its induced paths, then $G$ is dominated by a connected induced subgraph ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '18: Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures

July 2018

437 pages

ISBN:9781450357999

DOI:10.1145/3210377

General Chair:
Christian Scheideler
University of Paderborn, Germany
,
Program Chair:
Jeremy Fineman
Georgetown University, USA

Copyright © 2018 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].

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
EATCS: European Association for Theoretical Computer Science

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 July 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

ANR project Stint
ERC under European Union's Horizon 2020
National Science Centre of Poland POLONEZ
MaxPlanck Institute of Informatics
European Associated Laboratory ``Structures in Combinatorics'
Czech grant ERCCZ

Conference

SPAA '18

Sponsor:

SPAA '18: 30th ACM Symposium on Parallelism in Algorithms and Architectures

July 16 - 18, 2018

Vienna, Austria

Acceptance Rates

SPAA '18 Paper Acceptance Rate 36 of 120 submissions, 30%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
135
Total Downloads

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

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Heydt OKublenz SOssona de Mendez PSiebertz SVigny A(2025)Distributed domination on sparse graph classesEuropean Journal of Combinatorics10.1016/j.ejc.2023.103773123(103773)Online publication date: Jan-2025
https://doi.org/10.1016/j.ejc.2023.103773
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
Gorain BMondal KPandit S(2023)Distributed Dominating Sets in Interval GraphsComputing and Combinatorics10.1007/978-3-031-22105-7_45(508-520)Online publication date: 1-Jan-2023
https://doi.org/10.1007/978-3-031-22105-7_45
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
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
Kublenz SSiebertz SVigny A(2021)Constant Round Distributed Domination on Graph Classes with Bounded ExpansionStructural Information and Communication Complexity10.1007/978-3-030-79527-6_19(334-351)Online publication date: 20-Jun-2021
https://doi.org/10.1007/978-3-030-79527-6_19
Pescarin SFanini BFerdani DMifsud KHamilton A(2020)Optimising Environmental Educational Narrative VideogamesJournal on Computing and Cultural Heritage 10.1145/342495213:4(1-23)Online publication date: 3-Dec-2020
https://dl.acm.org/doi/10.1145/3424952
Plecher DHerber FEichhorn CPongratz ATanson GKlinker G(2020)HieroQuest - A Serious Game for Learning Egyptian HieroglyphsJournal on Computing and Cultural Heritage 10.1145/341803813:4(1-20)Online publication date: 3-Dec-2020
https://dl.acm.org/doi/10.1145/3418038
Fazio STurner J(2020)Bringing Empty Rooms to Life for Casual Visitors Using an AR Adventure GameJournal on Computing and Cultural Heritage 10.1145/341803713:4(1-21)Online publication date: 3-Dec-2020
https://dl.acm.org/doi/10.1145/3418037
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