License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2020.29
URN: urn:nbn:de:0030-drops-135149
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13514/
Faour, Salwa ;
Kuhn, Fabian
Approximating Bipartite Minimum Vertex Cover in the CONGEST Model
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²).
BibTeX - Entry
@InProceedings{faour_et_al:LIPIcs:2021:13514,
author = {Salwa Faour and Fabian Kuhn},
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 = {Quentin Bramas and Rotem Oshman and Paolo Romano},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13514},
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}
}
|
Keywords: |
|
distributed vertex cover, distributed graph algorithms, distributed optimization, bipartite vertex cover |
|
Collection: |
|
24th International Conference on Principles of Distributed Systems (OPODIS 2020) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
25.01.2021 |
