Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings

DOI10.4230/LIPICS.OPODIS.2021.17MaRDI QIDQ6128579zbMATH OpenOpenAlexFDO

Authors M. Fuchs, Fabian Kuhn

Publication date 15 April 2024

Full work available at URL https://arxiv.org/abs/2111.10577

zbMATH Keywords

CONGEST modeldistributed graph algorithmsdistributed optimizationmaximum weighted matchingminimum weighted vertex cover

Mathematics Subject Classification ID

Distributed systems (68M14) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

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+varepsilon)$-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-2lambda+varepsilon)$-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+varepsilon)$-approximate weighted vertex cover. For maximum weighted matchings, we show that a $(1-varepsilon)$-approximate solution can be computed deterministically in polylogarithmic CONGEST rounds (for constant $varepsilon$). 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 $leq3$, if $varepsilon<varepsilo{n}_0$ for some constant $varepsilo{n}_0>0$, then computing a $(1+varepsilon)$-approximation for the unweighted minimum vertex cover problem requires $$ rounds. This generalizes aresult of [G"o"os, Suomela; DISC '12], who showed that computing a $(1+varepsilo{n}_0)$-approximation in such graphs requires $Omega(logn)$ rounds.

Cited in

(1)

• Brief announcement: Low-distortion clustering in bounded growth graphs

This page was built for publication: Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6128579)