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 (22λ +ε)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 (21/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, PattShamir, Pettie; SPAA '08] and [BarYehuda, 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:117:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772198},
ISSN = {18688969},
year = {2022},
volume = {217},
editor = {Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15792},
URN = {urn:nbn:de:0030drops157928},
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 