Near-optimal distributed dominating set in bounded arboricity graphs
Abstract We describe a simple deterministic $$O( \varepsilon ^{-1} \log \Delta )$$ O ( ε...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2023
|
| Online Access: | https://hdl.handle.net/1721.1/150786 |
| Summary: | Abstract
We describe a simple deterministic
$$O( \varepsilon ^{-1} \log \Delta )$$
O
(
ε
-
1
log
Δ
)
round distributed algorithm for
$$(2\alpha +1)(1 + \varepsilon )$$
(
2
α
+
1
)
(
1
+
ε
)
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 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)$$
O
(
α
2
)
approximation in
$$O(\log n)$$
O
(
log
n
)
rounds (Lenzen et al. in International symposium on distributed computing, Springer, 2010), a deterministic
$$O(\alpha \log \Delta )$$
O
(
α
log
Δ
)
approximation in
$$O(\log \Delta )$$
O
(
log
Δ
)
rounds (Lenzen et al. in international symposium on distributed computing, Springer, 2010), a deterministic
$$O(\alpha )$$
O
(
α
)
approximation in
$$O(\log ^2 \Delta )$$
O
(
log
2
Δ
)
rounds (implicit in Bansal et al. in Inform Process Lett 122:21–24, 2017; Proceeding 17th symposium on discrete algorithms (SODA), 2006), and a randomized
$$O(\alpha )$$
O
(
α
)
approximation in
$$O(\alpha \log n)$$
O
(
α
log
n
)
rounds (Morgan et al. in 35th International symposiumon distributed computing, 2021). We also provide a randomized
$$O(\alpha \log \Delta )$$
O
(
α
log
Δ
)
round distributed algorithm that sharpens the approximation factor to
$$\alpha (1+o(1))$$
α
(
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 $$
α
-
1
-
ε
approximation (Bansal et al. in Inform Process Lett 122:21-24, 2017). |
|---|