License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2021.17
URN: urn:nbn:de:0030-drops-157928
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15792/
Faour, Salwa ;
Fuchs, Marc ;
Kuhn, Fabian
Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings
Abstract
We provide CONGEST model algorithms for approximating the minimum weighted vertex cover and the maximum weighted matching problem. For bipartite graphs, we show that a (1+ε)-approximate weighted vertex cover can be computed deterministically in poly((log n)/ε) rounds. This generalizes a corresponding result for the unweighted vertex cover problem shown in [Faour, Kuhn; OPODIS '20]. Moreover, we show that in general weighted graph families that are closed under taking subgraphs and in which we can compute an independent set of weight at least λ⋅ w(V) (where w(V) denotes the total weight of all nodes) in polylogarithmic time in the CONGEST model, one can compute a (2-2λ +ε)-approximate weighted vertex cover in poly((log n)/ε) rounds in the CONGEST model. Our result in particular implies that in graphs of arboricity a, one can compute a (2-1/a+ε)-approximate weighted vertex cover problem in poly((log n)/ε) rounds in the CONGEST model.
For maximum weighted matchings, we show that a (1-ε)-approximate solution can be computed deterministically in time 2^{O(1/ε)}⋅ polylog n in the CONGEST model. We also provide a randomized algorithm that with arbitrarily good constant probability succeeds in computing a (1-ε)-approximate weighted matching in time 2^{O(1/ε)}⋅ polylog(Δ W)⋅ log^* n, where W denotes the ratio between the largest and the smallest edge weight. Our algorithm generalizes results of [Lotker, Patt-Shamir, Pettie; SPAA '08] and [Bar-Yehuda, Hillel, Ghaffari, Schwartzman; PODC '17], who gave 2^{O(1/ε)}⋅ log n and 2^{O(1/ε)}⋅ (logΔ)/(log logΔ)-round randomized approximations for the unweighted matching problem.
Finally, we show that even in the LOCAL model and in bipartite graphs of degree ≤ 3, if ε < ε₀ for some constant ε₀ > 0, then computing a (1+ε)-approximation for the unweighted minimum vertex cover problem requires Ω((log n)/ε) rounds. This generalizes a result of [Göös, Suomela; DISC '12], who showed that computing a (1+ε₀)-approximation in such graphs requires Ω(log n) rounds.
BibTeX - Entry
@InProceedings{faour_et_al:LIPIcs.OPODIS.2021.17,
author = {Faour, Salwa and Fuchs, Marc and Kuhn, Fabian},
title = {{Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings}},
booktitle = {25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
pages = {17:1--17:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-219-8},
ISSN = {1868-8969},
year = {2022},
volume = {217},
editor = {Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15792},
URN = {urn:nbn:de:0030-drops-157928},
doi = {10.4230/LIPIcs.OPODIS.2021.17},
annote = {Keywords: distributed graph algorithms, minimum weighted vertex cover, maximum weighted matching, distributed optimization, CONGEST model}
}
|
Keywords: |
|
distributed graph algorithms, minimum weighted vertex cover, maximum weighted matching, distributed optimization, CONGEST model |
|
Collection: |
|
25th International Conference on Principles of Distributed Systems (OPODIS 2021) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
28.02.2022 |
