Near-Optimal Distributed Dominating Set in Bounded Arboricity Graphs
METADATA ONLY
Loading...
Author / Producer
Date
2022-07
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
We describe a simple deterministic O(-1 log ") round distributed algorithm for (2α+ 1) (1 + ) approximation of minimum weighted dominating set on graphs with arboricity at most α. Here Δ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(α2) approximation inO(logn) rounds [Lenzen andWattenhofer DISC'10], a deterministic O(α log ") approximation in O(log ") rounds [Lenzen and Wattenhofer DISC'10], a deterministic O(α) approximation in O(log2 ") rounds [implicit in Bansal and Umboh IPL'17 and Kuhn, Moscibroda, and Wattenhofer SODA'06], and a randomized O(α) approximation in O(α logn) rounds [Morgan, Solomon and Wein DISC'21]. We also provide a randomized O(α log ") round distributed algorithm that sharpens the approximation factor to α (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 α - 1 - approximation [Bansal and Umboh IPL'17].
Permanent link
Publication status
published
External links
Editor
Book title
PODC'22: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing
Journal / series
Volume
Pages / Article No.
292 - 300
Publisher
Association for Computing Machinery
Event
Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (PODC 2022)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Distributed Computing; Dominating Set; Arboricity; Approximation Algorithms
Organisational unit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
09587 - Ghaffari, Mohsen (ehemalig) / Ghaffari, Mohsen (former)
Notes
Funding
184735 - Distributed Algorithms for Global Graph Problems (SNF)
Related publications and datasets
Is previous version of: