Document Open Access Logo

Approximating Bipartite Minimum Vertex Cover in the CONGEST Model

Authors Salwa Faour, Fabian Kuhn

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2020.29.pdf
  • Filesize: 0.52 MB
  • 16 pages

Document Identifiers

Author Details

Salwa Faour
  • Albert-Ludwigs-Universität Freiburg, Germany
Fabian Kuhn
  • Albert-Ludwigs-Universität Freiburg, Germany

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.OPODIS.2020.29

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²).

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Networks → Network algorithms
Keywords
  • distributed vertex cover
  • distributed graph algorithms
  • distributed optimization
  • bipartite vertex cover

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. M. Ahmadi, F. Kuhn, and R. Oshman. Distributed approximate maximum matching in the CONGEST model. In Proc. 32nd Symp. on Distributed Computing (DISC), pages 6:1-6:17, 2018. Google Scholar
  2. N. Alon, L. Babai, and A. Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. Journal of Algorithms, 7(4):567-583, 1986. Google Scholar
  3. M. Åstrand, P. Floréen, V. Polishchuk, J. Rybicki, J. Suomela, and J. Uitto. A local 2-approximation algorithm for the vertex cover problem. In Proc. 23rd Symp. on Distributed Computing (DISC), pages 191-205, 2009. Google Scholar
  4. N. Bachrach, K. Censor-Hillel, M. Dory, Y. Efron, D. Leitersdorf, and A. Paz. Hardness of distributed optimization. In Proc. 38th ACM Symp. on Principles of Distributed Computing (PODC), pages 238-247, 2019. Google Scholar
  5. R. Bar-Yehuda, K. Censor-Hillel, M. Ghaffari, and G. Schwartzman. Distributed approximation of maximum independent set and maximum matching. CoRR, abs/1708.00276, 2017. Conference version at PODC 2017. Google Scholar
  6. R. Bar-Yehuda, K. Censor-Hillel, Y. Maus, S. Pai, and S. V. Pemmaraju. Distributed approximation on power graphs. In Proc. 39th ACM Symp. on Principles of Distributed Computing (PODC), pages 501-510, 2020. Google Scholar
  7. R. Bar-Yehuda, K. Censor-Hillel, and G. Schwartzman. A distributed (2+ε)-approximation for vertex cover in o(logδ/ε log log δ) rounds. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 3-8, 2016. Google Scholar
  8. L. Barenboim, M. Elkin, S. Pettie, and J. Schneider. The locality of distributed symmetry breaking. In Proceedings of 53th Symposium on Foundations of Computer Science (FOCS), 2012. Google Scholar
  9. R. Ben-Basat, G. Even, K. Kawarabayashi, and G. Schwartzman. Optimal distributed covering algorithms. In Proc. 33rd Symp. on Distributed Computing (DISC), pages 5:1-5:15, 2019. Google Scholar
  10. G. E. Blelloch, A. Gupta, I. Koutis, G. L. Miller, R. Peng, and K. Tangwongsan. Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs. Theory Comput. Syst., 55(3):521-554, 2014. Google Scholar
  11. K. Censor-Hillel, S. Khoury, and A. Paz. Quadratic and near-quadratic lower bounds for the CONGEST model. In Proc. 31st Symp. on Distributed Computing (DISC), pages 10:1-10:16, 2017. Google Scholar
  12. R. Diestel. Graph Theory, chapter 2.1, pages 35-58. Springer, Berlin, 3rd edition, 2005. Google Scholar
  13. S. Faour and F. Kuhn. Approximate bipartite vertex cover in the CONGEST model. CoRR, abs/2011.10014, 2020. Google Scholar
  14. U. Feige, Y. Mansour, and R. E. Schapire. Learning and inference in the presence of corrupted inputs. In Proc. 28th Conf. on Learning Theory (COLT), pages 637-657, 2015. Google Scholar
  15. M. Fischer. Improved deterministic distributed matching via rounding. In Proc. 31st Symp. on Distributed Computing (DISC), pages 17:1-17:15, 2017. Google Scholar
  16. M. Ghaffari, C. Jin, and D. Nilis. A massively parallel algorithm for minimum weight vertex cover. In Proc. 32nd ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pages 259-268, 2020. Google Scholar
  17. M. Ghaffari, F. Kuhn, and Y. Maus. On the complexity of local distributed graph problems. In Proc. 39th ACM Symp. on Theory of Computing (STOC), pages 784-797, 2017. Google Scholar
  18. M. Göös and J. Suomela. No sublogarithmic-time approximation scheme for bipartite vertex cover. Distributed Computing, 27(6):435-443, 2014. Google Scholar
  19. F. Grandoni, J. Könemann, and A. Panconesi. Distributed weighted vertex cover via maximal matchings. ACM Trans. Algorithms, 5(1):6:1-6:12, 2008. Google Scholar
  20. F. Grandoni, J. Könemann, A. Panconesi, and M. Sozio. A primal-dual bicriteria distributed algorithm for capacitated vertex cover. SIAM J. Comput., 38(3):825-840, 2008. Google Scholar
  21. J. E. Hopcroft and R. M. Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 1973. Google Scholar
  22. A. Israeli and A. Itai. A fast and simple randomized parallel algorithm for maximal matching. Inf. Process. Lett., 22(2):77-80, 1986. Google Scholar
  23. D. Kőnig. Gráfok és mátrixok. Matematikai és Fizikai Lapok, 38:116-119, 1931. Google Scholar
  24. Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci., 74(3):335-349, 2008. Google Scholar
  25. F. Kuhn, T. Moscibroda, and R. Wattenhofer. What cannot be computed locally! In Proceedings of 23rd ACM Symposium on Principles of Distributed Computing (PODC), pages 300-309, 2004. Google Scholar
  26. F. Kuhn, T. Moscibroda, and R. Wattenhofer. The price of being near-sighted. In Proceedings of 17th Symposium on Discrete Algorithms (SODA), pages 980-989, 2006. Google Scholar
  27. N. Linial and M. Saks. Low diameter graph decompositions. Combinatorica, 13(4):441-454, 1993. Google Scholar
  28. Z. Lotker, B. Patt-Shamir, and S. Pettie. Improved distributed approximate matching. J. ACM, 62(5):38:1-38:17, 2015. Google Scholar
  29. M. Luby. A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing, 15:1036-1053, 1986. Google Scholar
  30. G. L. Miller, R. Peng, and S. C. Xu. Parallel graph decompositions using random shifts. In Proc. 25th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pages 196-203, 2013. Google Scholar
  31. D. Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000. Google Scholar
  32. V. Rozhoň and M. Ghaffari. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In Proc. 52nd ACM Symp. on Theory of Computing (STOC), pages 350-363, 2020. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact