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 |
| _version_ | 1811086448378511360 |
|---|---|
| author | Dory, Michal Ghaffari, Mohsen Ilchi, Saeed |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Dory, Michal Ghaffari, Mohsen Ilchi, Saeed |
| author_sort | Dory, Michal |
| collection | MIT |
| description | 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). |
| first_indexed | 2024-09-23T13:26:05Z |
| format | Article |
| id | mit-1721.1/150786 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:26:05Z |
| publishDate | 2023 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1507862024-01-10T18:06:40Z Near-optimal distributed dominating set in bounded arboricity graphs Dory, Michal Ghaffari, Mohsen Ilchi, Saeed Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science 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). 2023-05-22T13:52:02Z 2023-05-22T13:52:02Z 2023-05-15 2023-05-21T03:12:00Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/150786 Dory, Michal, Ghaffari, Mohsen and Ilchi, Saeed. 2023. "Near-optimal distributed dominating set in bounded arboricity graphs." PUBLISHER_CC en https://doi.org/10.1007/s00446-023-00447-z Creative Commons Attribution http://creativecommons.org/licenses/by/4.0/ The Author(s) application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Dory, Michal Ghaffari, Mohsen Ilchi, Saeed Near-optimal distributed dominating set in bounded arboricity graphs |
| title | Near-optimal distributed dominating set in bounded arboricity graphs |
| title_full | Near-optimal distributed dominating set in bounded arboricity graphs |
| title_fullStr | Near-optimal distributed dominating set in bounded arboricity graphs |
| title_full_unstemmed | Near-optimal distributed dominating set in bounded arboricity graphs |
| title_short | Near-optimal distributed dominating set in bounded arboricity graphs |
| title_sort | near optimal distributed dominating set in bounded arboricity graphs |
| url | https://hdl.handle.net/1721.1/150786 |
| work_keys_str_mv | AT dorymichal nearoptimaldistributeddominatingsetinboundedarboricitygraphs AT ghaffarimohsen nearoptimaldistributeddominatingsetinboundedarboricitygraphs AT ilchisaeed nearoptimaldistributeddominatingsetinboundedarboricitygraphs |