{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:39:01Z","timestamp":1782970741094,"version":"3.54.5"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T00:00:00Z","timestamp":1684108800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T00:00:00Z","timestamp":1684108800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"HORIZON EUROPE European Research Council,European Union","award":["853109"],"award-info":[{"award-number":["853109"]}]},{"name":"HORIZON EUROPE European Research Council,European Union","award":["853109"],"award-info":[{"award-number":["853109"]}]},{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["200021-184735"],"award-info":[{"award-number":["200021-184735"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["200021-184735"],"award-info":[{"award-number":["200021-184735"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Swiss Federal Institute of Technology Zurich"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2024,12]]},"abstract":"Abstract<\/jats:title>We describe a simple deterministic $$O( \\varepsilon ^{-1} \\log \\Delta )$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n \u03b5<\/mml:mi>\n \n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n log<\/mml:mo>\n \u0394<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> round distributed algorithm for $$(2\\alpha +1)(1 + \\varepsilon )$$<\/jats:tex-math>\n \n (<\/mml:mo>\n 2<\/mml:mn>\n \u03b1<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n (<\/mml:mo>\n 1<\/mml:mn>\n +<\/mml:mo>\n \u03b5<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> approximation of minimum weighted dominating set on graphs with arboricity at most $$\\alpha $$<\/jats:tex-math>\n \u03b1<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Here $$\\Delta $$<\/jats:tex-math>\n \u0394<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> denotes the maximum degree. We also show a lower bound proving that this round complexity is nearly optimal even for the unweighted case, via a reduction from the celebrated KMW lower bound on distributed vertex cover approximation (Kuhn et al. in JACM 63:116, 2016). Our algorithm improves on all the previous results (that work only for unweighted graphs) including a randomized $$O(\\alpha ^2)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n \u03b1<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> approximation in $$O(\\log n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> rounds (Lenzen et al. in International symposium on distributed computing, Springer, 2010), a deterministic $$O(\\alpha \\log \\Delta )$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \u03b1<\/mml:mi>\n log<\/mml:mo>\n \u0394<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> approximation in $$O(\\log \\Delta )$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n \u0394<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> rounds (Lenzen et al. in international symposium on distributed computing, Springer, 2010), a deterministic $$O(\\alpha )$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \u03b1<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> approximation in $$O(\\log ^2 \\Delta )$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n log<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:msup>\n \u0394<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> rounds (implicit in Bansal et al. in Inform Process Lett 122:21\u201324, 2017; Proceeding 17th symposium on discrete algorithms (SODA), 2006), and a randomized $$O(\\alpha )$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \u03b1<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> approximation in $$O(\\alpha \\log n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \u03b1<\/mml:mi>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> rounds (Morgan et al. in 35th International symposiumon distributed computing, 2021). We also provide a randomized $$O(\\alpha \\log \\Delta )$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \u03b1<\/mml:mi>\n log<\/mml:mo>\n \u0394<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> round distributed algorithm that sharpens the approximation factor to $$\\alpha (1+o(1))$$<\/jats:tex-math>\n \n \u03b1<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n +<\/mml:mo>\n o<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. If each node is restricted to do polynomial-time computations, our approximation factor is tight in the first order as it is NP-hard to achieve $$\\alpha - 1 - \\varepsilon $$<\/jats:tex-math>\n \n \u03b1<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n -<\/mml:mo>\n \u03b5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> approximation (Bansal et al. in Inform Process Lett 122:21-24, 2017).<\/jats:p>","DOI":"10.1007\/s00446-023-00447-z","type":"journal-article","created":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T15:25:45Z","timestamp":1684164345000},"page":"387-398","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Near-optimal distributed dominating set in bounded arboricity graphs"],"prefix":"10.1007","volume":"37","author":[{"given":"Michal","family":"Dory","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohsen","family":"Ghaffari","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saeed","family":"Ilchi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,5,15]]},"reference":[{"key":"447_CR1","doi-asserted-by":"crossref","unstructured":"Akhoondian Amiri S., Ossona de Mendez P., Rabinovich R., et al.: Distributed domination on graph classes of bounded expansion. In: Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA), pp 143\u2013151 (2018)","DOI":"10.1145\/3210377.3210383"},{"key":"447_CR2","unstructured":"Amiri, S.A.: Deterministic CONGEST algorithm for MDS on bounded arboricity graphs. CoRR abs\/2102.08076 (2021)"},{"issue":"3","key":"447_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3326170","volume":"15","author":"SA Amiri","year":"2019","unstructured":"Amiri, S.A., Schmid, S., Siebertz, S.: Distributed dominating set approximations beyond planar graphs. ACM Transact Algorithm (TALG) 15(3), 1\u201318 (2019)","journal-title":"ACM Transact Algorithm (TALG)"},{"key":"447_CR4","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/j.ipl.2017.01.011","volume":"122","author":"N Bansal","year":"2017","unstructured":"Bansal, N., Umboh, S.W.: Tight approximation bounds for dominating set on graphs of bounded arboricity. Inform. Process. Lett. 122, 21\u201324 (2017)","journal-title":"Inform. Process. Lett."},{"issue":"5","key":"447_CR5","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/s00446-009-0088-2","volume":"22","author":"L Barenboim","year":"2010","unstructured":"Barenboim, L., Elkin, M.: Sublogarithmic distributed mis algorithm for sparse graphs using nash-williams decomposition. Distrib. Comput. 22(5), 363\u2013379 (2010)","journal-title":"Distrib. Comput."},{"key":"447_CR6","unstructured":"Bonamy, M., Cook, L., Groenland, C., et\u00a0al.: A tight local algorithm for the minimum dominating set problem in outerplanar graphs. In: 35th International Symposium on Distributed Computing, DISC 2021, LIPIcs, vol 209. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp 13:1\u201313:18 (2021)"},{"key":"447_CR7","unstructured":"Cambus, M., Choo, D., Miikonen, H., et\u00a0al.: Massively parallel correlation clustering in bounded arboricity graphs. In: 35th International Symposium on Distributed Computing, DISC 2021, LIPIcs, vol 209. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp 15:1\u201315:18 (2021)"},{"key":"447_CR8","doi-asserted-by":"crossref","unstructured":"Czygrinow, A., Ha\u0144\u0107kowiak, M., Wawrzyniak, W.: Fast distributed approximations in planar graphs. In: International Symposium on Distributed Computing, Springer, pp 78\u201392 (2008)","DOI":"10.1007\/978-3-540-87779-0_6"},{"key":"447_CR9","doi-asserted-by":"crossref","unstructured":"Deurer, J., Kuhn, F., Maus, Y.: Deterministic distributed dominating set approximation in the congest model. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC), pp 94\u2013103 (2019)","DOI":"10.1145\/3293611.3331626"},{"key":"447_CR10","doi-asserted-by":"crossref","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pp 624\u2013633 (2014)","DOI":"10.1145\/2591796.2591884"},{"issue":"2","key":"447_CR11","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1002\/jgt.22426","volume":"91","author":"Z Dvo\u0159\u00e1k","year":"2019","unstructured":"Dvo\u0159\u00e1k, Z.: On distance-dominating and-independent sets in sparse graphs. J. Graph Theory 91(2), 162\u2013173 (2019)","journal-title":"J. Graph Theory"},{"issue":"2","key":"447_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3381418","volume":"16","author":"T Eden","year":"2020","unstructured":"Eden, T., Levi, R., Ron, D.: Testing bounded arboricity. ACM Transact. Algorithms (TALG) 16(2), 1\u201322 (2020)","journal-title":"ACM Transact. Algorithms (TALG)"},{"key":"447_CR13","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Kuhn, F., Maus, Y.: On the complexity of local distributed graph problems. In: Proc. 49th ACM Symp. on Theory of Computing (STOC), pp 784\u2013797 (2017)","DOI":"10.1145\/3055399.3055471"},{"key":"447_CR14","doi-asserted-by":"crossref","unstructured":"Gianinazzi, L., Besta, M., Schaffner, Y., et\u00a0al.: Parallel algorithms for finding large cliques in sparse graphs. In: Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp 243\u2013253 (2021)","DOI":"10.1145\/3409964.3461800"},{"key":"447_CR15","doi-asserted-by":"crossref","unstructured":"Goel, G., Gustedt, J.: Bounded arboricity to determine the local structure of sparse graphs. In: International Workshop on Graph-Theoretic Concepts in Computer Science, Springer, pp 159\u2013167 (2006)","DOI":"10.1007\/11917496_15"},{"issue":"4","key":"447_CR16","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s00446-002-0078-0","volume":"15","author":"L Jia","year":"2002","unstructured":"Jia, L., Rajaraman, R., Suel, T.: An efficient distributed algorithm for constructing small dominating sets. Distrib. Comput. 15(4), 193\u2013205 (2002)","journal-title":"Distrib. Comput."},{"issue":"3","key":"447_CR17","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9(3), 256\u2013278 (1974)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"447_CR18","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/s00446-004-0112-5","volume":"17","author":"F Kuhn","year":"2005","unstructured":"Kuhn, F., Wattenhofer, R.: Constant-time distributed dominating set approximation. Distrib. Comput. 17(4), 303\u2013310 (2005)","journal-title":"Distrib. Comput."},{"key":"447_CR19","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: Proceeding 17th Symposium on Discrete Algorithms (SODA), pp 980\u2013989 (2006)","DOI":"10.1145\/1109557.1109666"},{"key":"447_CR20","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: Local computation: Lower and upper bounds. JACM 63(2) (2016)","DOI":"10.1145\/2742012"},{"key":"447_CR21","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Wattenhofer, R.: Minimum dominating set approximation in graphs of bounded arboricity. In: International symposium on distributed computing (DISC), Springer, pp 510\u2013524 (2010)","DOI":"10.1007\/978-3-642-15763-9_48"},{"key":"447_CR22","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Oswald, YA., Wattenhofer, R.: What can be approximated locally? case study: Dominating sets in planar graphs. In: Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures (SPAA), pp 46\u201354 (2008)","DOI":"10.1145\/1378533.1378540"},{"issue":"2","key":"447_CR23","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/s00446-013-0186-z","volume":"26","author":"C Lenzen","year":"2013","unstructured":"Lenzen, C., Pignolet, Y.A., Wattenhofer, R.: Distributed minimum dominating set approximations in restricted families of graphs. Distrib. Comput. 26(2), 119\u2013137 (2013)","journal-title":"Distrib. Comput."},{"key":"447_CR24","unstructured":"Morgan, A., Solomon, S., Wein, N.: Algorithms for the minimum dominating set problem in bounded arboricity graphs: Simpler, faster, and combinatorial. In: 35th International Symposium on Distributed Computing, DISC 2021, LIPIcs, vol 209. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp 33:1\u201333:19 (2021)"},{"key":"447_CR25","doi-asserted-by":"crossref","unstructured":"Rozho\u0148, V., Ghaffari, M.: Polylogarithmic-time deterministic network decomposition and distributed derandomization. In: Proc. 52nd ACM Symp. on Theory of Computing (STOC), pp 350\u2013363 (2020)","DOI":"10.1145\/3357713.3384298"},{"key":"447_CR26","doi-asserted-by":"crossref","unstructured":"Sun, H.: An improved approximation bound for minimum weight dominating set on graphs of bounded arboricity. In: International Workshop on Approximation and Online Algorithms, Springer, pp 39\u201347 (2021)","DOI":"10.1007\/978-3-030-92702-8_3"},{"issue":"3","key":"447_CR27","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.ipl.2013.11.008","volume":"114","author":"W Wawrzyniak","year":"2014","unstructured":"Wawrzyniak, W.: A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs. Inform. Process. Lett. 114(3), 94\u201398 (2014)","journal-title":"Inform. Process. Lett."}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-023-00447-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-023-00447-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-023-00447-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T09:11:04Z","timestamp":1730970664000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-023-00447-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,15]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["447"],"URL":"https:\/\/doi.org\/10.1007\/s00446-023-00447-z","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,15]]},"assertion":[{"value":"16 November 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 March 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 May 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declaration"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}