DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2021.17

Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings

Authors: Salwa Faour, Marc Fuchs, and Fabian Kuhn

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

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.

Cite as

Salwa Faour, Marc Fuchs, and Fabian Kuhn. Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.OPODIS.2021.17},
  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}
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2020.29

Approximating Bipartite Minimum Vertex Cover in the CONGEST Model

Authors: Salwa Faour and Fabian Kuhn

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

Abstract

We give efficient distributed algorithms for the minimum vertex cover problem in bipartite graphs in the CONGEST model. From Kőnig’s theorem, it is well known that in bipartite graphs the size of a minimum vertex cover is equal to the size of a maximum matching. We first show that together with an existing O(nlog n)-round algorithm for computing a maximum matching, the constructive proof of Kőnig’s theorem directly leads to a deterministic O(nlog n)-round CONGEST algorithm for computing a minimum vertex cover. We then show that by adapting the construction, we can also convert an approximate maximum matching into an approximate minimum vertex cover. Given a (1-δ)-approximate matching for some δ > 1, we show that a (1+O(δ))-approximate vertex cover can be computed in time O (D+poly((log n)/δ)), where D is the diameter of the graph. When combining with known graph clustering techniques, for any ε ∈ (0,1], this leads to a poly((log n)/ε)-time deterministic and also to a slightly faster and simpler randomized O((log n)/ε³)-round CONGEST algorithm for computing a (1+ε)-approximate vertex cover in bipartite graphs. For constant ε, the randomized time complexity matches the Ω(log n) lower bound for computing a (1+ε)-approximate vertex cover in bipartite graphs even in the LOCAL model. Our results are also in contrast to the situation in general graphs, where it is known that computing an optimal vertex cover requires Ω̃(n²) rounds in the CONGEST model and where it is not even known how to compute any (2-ε)-approximation in time o(n²).

Cite as

Salwa Faour and Fabian Kuhn. Approximating Bipartite Minimum Vertex Cover in the CONGEST Model. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{faour_et_al:LIPIcs.OPODIS.2020.29,
  author =	{Faour, Salwa and Kuhn, Fabian},
  title =	{{Approximating Bipartite Minimum Vertex Cover in the CONGEST Model}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.29},
  URN =		{urn:nbn:de:0030-drops-135149},
  doi =		{10.4230/LIPIcs.OPODIS.2020.29},
  annote =	{Keywords: distributed vertex cover, distributed graph algorithms, distributed optimization, bipartite vertex cover}
}

Search Results

Documents authored by Faour, Salwa

Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings

Abstract

Cite as

Approximating Bipartite Minimum Vertex Cover in the CONGEST Model

Abstract

Cite as

Thanks for your feedback!

Could not send message