Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings

Abstract

We provide CONGEST model algorithms for approximating minimum weighted vertex cover and the maximum weighted matching. For bipartite graphs, we show that a $(1+\epsilon )$-approximate weighted vertex cover can be computed deterministically in polylogarithmic time. 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 a $\lambda$-fraction of the total weight, one can compute a $(2-2\lambda +\epsilon )$-approximate weighted vertex cover in polylogarithmic time in the CONGEST model. Our result in particular implies that in graphs of arboricity $a$, one can compute a $(2-1/a+\epsilon )$-approximate weighted vertex cover. For maximum weighted matchings, we show that a $(1-\epsilon )$-approximate solution can be computed deterministically in polylogarithmic CONGEST rounds (for constant $\epsilon$). We also provide a more efficient randomized algorithm. Our algorithm generalizes results of [Lotker, Patt-Shamir, Pettie; SPAA '08] and [Bar-Yehuda, Hillel, Ghaffari, Schwartzman; PODC '17] for the unweighted case. Finally, we show that even in the LOCAL model and in bipartite graphs of degree $\le 3$, if $\epsilon <{\epsilon }_0$ for some constant ${\epsilon }_0>0$, then computing a $(1+\epsilon )$-approximation for the unweighted minimum vertex cover problem requires $\Omega \left(\frac{\log n}{\epsilon }\right)$ rounds. This generalizes aresult of [Göös, Suomela; DISC '12], who showed that computing a $(1+{\epsilon }_0)$-approximation in such graphs requires $\Omega (\log n)$ rounds.

References in corpus (2)

• Distributed algorithms for covering, packing and maximum weighted matching
• Brief Announcement: Does Preprocessing Help under Congestion?