Near-Optimal Distributed Dominating Set in Bounded Arboricity Graphs

DOI10.1145/3519270.3538437MaRDI QIDQ6202173zbMATH OpenOpenAlexWikidataFDO

Authors Michal Dory, Mohsen Ghaffari, Saeed Gh. Ilchi

Publication date 26 March 2024

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

Full work available at URL https://arxiv.org/abs/2206.05174, http://hdl.handle.net/20.500.11850/615188

zbMATH Keywords

approximation algorithmsarboricitydistributed computingdominating set

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Abstract: We describe a simple deterministic $O(varepsilo{n}^{-1}logDelta)$ round distributed algorithm for $(2alpha+1)(1+varepsilon)$ approximation of minimum weighted dominating set on graphs with arboricity at most $alpha$. Here $Delta$ 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, Moscibroda, and Wattenhofer JACM'16]. Our algorithm improves on all the previous results (that work only for unweighted graphs) including a randomized $O(alph{a}^2)$ approximation in $O(logn)$ rounds [Lenzen and Wattenhofer DISC'10], a deterministic $O(alphalogDelta)$ approximation in $O(logDelta)$ rounds [Lenzen and Wattenhofer DISC'10], a deterministic $O(alpha)$ approximation in $O(lo{g}^{2}Delta)$ rounds [implicit in Bansal and Umboh IPL'17 and Kuhn, Moscibroda, and Wattenhofer SODA'06], and a randomized $O(alpha)$ approximation in $O(alphalogn)$ rounds [Morgan, Solomon and Wein DISC'21]. We also provide a randomized $O(alphalogDelta)$ round distributed algorithm that sharpens the approximation factor to $alpha(1+o(1))$. 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$ approximation [Bansal and Umboh IPL'17].

Cited in

(1)

• Distributed domination on sparse graph classes

This page was built for publication: Near-Optimal Distributed Dominating Set in Bounded Arboricity Graphs

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