Article

A local 2-approximation algorithm for the vertex cover problem

Authors:

Matti Åstrand,

Patrik Floréen,

Valentin Polishchuk,

Jara UittoAuthors Info & Claims

DISC'09: Proceedings of the 23rd international conference on Distributed computing

Pages 191 - 205

Published: 23 September 2009 Publication History

Abstract

We present a distributed 2-approximation algorithm for the minimum vertex cover problem. The algorithm is deterministic, and it runs in (Δ + 1)² synchronous communication rounds, where Δ is the maximum degree of the graph. For Δ = 3, we give a 2-approximation algorithm also for the weighted version of the problem.

References

[1]

Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85-103. Plenum Press, New York (1972).

[2]

Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979).

[3]

Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2 - Ɛ. Journal of Computer and System Sciences 74(3), 335-349 (2008).

[4]

Grandoni, F., Könemann, J., Panconesi, A.: Distributed weighted vertex cover via maximal matchings. ACM Transactions on Algorithms 5(1), 1-12 (2008).

[5]

Hanckowiak, M., Karonski, M., Panconesi, A.: On the distributed complexity of computing maximal matchings. SIAM Journal on Discrete Mathematics 15(1), 41- 57 (2001).

[6]

Panconesi, A., Rizzi, R.: Some simple distributed algorithms for sparse networks. Distributed Computing 14(2), 97-100 (2001).

[7]

Linial, N.: Locality in distributed graph algorithms. SIAM Journal on Computing 21(1), 193-201 (1992).

[8]

Naor, M., Stockmeyer, L.: What can be computed locally? SIAM Journal on Computing 24(6), 1259-1277 (1995).

[9]

Suomela, J.: Survey of local algorithms (2009, manuscript), http://www.iki.fi/jukka.suomela/local-survey

[10]

Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: Proc. 23rd Symposium on Principles of Distributed Computing (PODC), pp. 300-309. ACM Press, New York (2004).

[11]

Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: Proc. 17th Symposium on Discrete Algorithms (SODA), pp. 980-989. ACM Press, New York (2006).

[12]

Hochbaum, D.S.: Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on Computing 11(3), 555-556 (1982).

[13]

Moscibroda, T.: Locality, Scheduling, and Selfishness: Algorithmic Foundations of Highly Decentralized Networks. PhD thesis, ETH Zürich (2006).

[14]

Polishchuk, V., Suomela, J.: A simple local 3-approximation algorithm for vertex cover. Information Processing Letters 109(12), 642-645 (2009).

[15]

Czygrinow, A., Hanckowiak, M., Wawrzyniak, W.: Fast distributed approximations in planar graphs. In: Taubenfeld, G. (ed.) DISC 2008. LNCS, vol. 5218, pp. 78-92. Springer, Heidelberg (2008).

[16]

Lenzen, C., Wattenhofer, R.: Leveraging Linial's locality limit. In: Taubenfeld, G. (ed.) DISC 2008. LNCS, vol. 5218, pp. 394-407. Springer, Heidelberg (2008).

[17]

Awerbuch, B., Varghese, G.: Distributed program checking: a paradigm for building self-stabilizing distributed protocols. In: Proc. 32nd Symposium on Foundations of Computer Science (FOCS), pp. 258-267. IEEE Computer Society Press, Los Alamitos (1991).

[18]

Bar-Yehuda, R., Even, S.: A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms 2(2), 198-203 (1981).

[19]

Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, Heidelberg (2003).

[20]

Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001).

[21]

Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Dover Publications, New York (1998).

[22]

Gonzalez, T.F.: A simple LP-free approximation algorithm for the minimum weight vertex cover problem. Information Processing Letters 54(3), 129-131 (1995).

[23]

Khuller, S., Vishkin, U., Young, N.: A primal-dual parallel approximation technique applied to weighted set and vertex covers. Journal of Algorithms 17(2), 280-289 (1994).

[24]

Hanckowiak, M., Karonski, M., Panconesi, A.: On the distributed complexity of computing maximal matchings. In: Proc. 9th Symposium on Discrete Algorithms (SODA), pp. 219-225. SIAM, Philadelphia (1998).

[25]

Ramsey, F.P.: On a problem of formal logic. Proceedings of the London Mathematical Society 30, 264-286 (1930).

[26]

Floréen, P., Kaasinen, J., Kaski, P., Suomela, J.: An optimal local approximation algorithm for max-min linear programs. In: Proc. 21st Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM Press, New York (2009).

[27]

Mayer, A., Naor, M., Stockmeyer, L.: Local computations on static and dynamic graphs. In: Proc. 3rd Israel Symposium on the Theory of Computing and Systems (ISTCS 1995), pp. 268-278. IEEE Computer Society Press, Los Alamitos (1995).

Cited By

Ben Basat REven GKawarabayashi KSchwartzman GRobinson PEllen F(2019)Optimal Distributed Covering AlgorithmsProceedings of the 2019 ACM Symposium on Principles of Distributed Computing10.1145/3293611.3331577(104-106)Online publication date: 16-Jul-2019
https://dl.acm.org/doi/10.1145/3293611.3331577
Bar-Yehuda RCensor-Hillel KSchwartzman G(2017)A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) RoundsJournal of the ACM10.1145/306029464:3(1-11)Online publication date: 16-Jun-2017
https://dl.acm.org/doi/10.1145/3060294
Bar-Yehuda RCensor-Hillel KSchwartzman GGiakkoupis G(2016)A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) RoundsProceedings of the 2016 ACM Symposium on Principles of Distributed Computing10.1145/2933057.2933086(3-8)Online publication date: 25-Jul-2016
https://dl.acm.org/doi/10.1145/2933057.2933086
Show More Cited By

A local 2-approximation algorithm for the vertex cover problem
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
    2. Graph theory
  2. Mathematical analysis
    1. Functional analysis

Recommendations

A 2-approximation NC algorithm for connected vertex cover and tree cover

The connected vertex cover problem is a variant of the vertex cover problem, in which a vertex cover is additional required to induce a connected subgraph in a given connected graph. The problem is known to be NP-hard and to be at least as hard to ...
An approximation algorithm for the partial vertex cover problem in hypergraphs

Let $$\mathcal {H}=(V,\mathcal {E})$$H=(V,E) be a hypergraph with set of vertices $$V, n:=|V|$$V,n:=|V| and set of (hyper-)edges $$\mathcal {E}, m:=|\mathcal {E}|$$E,m:=|E|. Let $$l$$l be the maximum size of an edge, $$\varDelta $$Δ be the maximum ...
Complexity and approximation results for the connected vertex cover problem
WG'07: Proceedings of the 33rd international conference on Graph-theoretic concepts in computer science

We study a variation of the vertex cover problem where it is required that the graph induced by the vertex cover is connected. We prove that this problem is polynomial in chordal graphs, has a PTAS in planar graphs, is APX-hard in bipartite graphs and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

DISC'09: Proceedings of the 23rd international conference on Distributed computing

September 2009

532 pages

ISBN:3642043542

Editor:
Idit Keidar
Technion - Israel Institute of Technology, Department of Electrical Engineering, Haifa, Israel

In-Cooperation

EATCS: European Association for Theoretical Computer Science

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 23 September 2009

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
4
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ben Basat REven GKawarabayashi KSchwartzman GRobinson PEllen F(2019)Optimal Distributed Covering AlgorithmsProceedings of the 2019 ACM Symposium on Principles of Distributed Computing10.1145/3293611.3331577(104-106)Online publication date: 16-Jul-2019
https://dl.acm.org/doi/10.1145/3293611.3331577
Bar-Yehuda RCensor-Hillel KSchwartzman G(2017)A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) RoundsJournal of the ACM10.1145/306029464:3(1-11)Online publication date: 16-Jun-2017
https://dl.acm.org/doi/10.1145/3060294
Bar-Yehuda RCensor-Hillel KSchwartzman GGiakkoupis G(2016)A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) RoundsProceedings of the 2016 ACM Symposium on Principles of Distributed Computing10.1145/2933057.2933086(3-8)Online publication date: 25-Jul-2016
https://dl.acm.org/doi/10.1145/2933057.2933086
Göös MHirvonen JSuomela JHalldórsson MDolev S(2014)Linear-in-delta lower bounds in the LOCAL modelProceedings of the 2014 ACM symposium on Principles of distributed computing10.1145/2611462.2611467(86-95)Online publication date: 15-Jul-2014
https://dl.acm.org/doi/10.1145/2611462.2611467
Göös MHirvonen JSuomela J(2013)Lower bounds for local approximationJournal of the ACM10.1145/252840560:5(1-23)Online publication date: 28-Oct-2013
https://dl.acm.org/doi/10.1145/2528405
Suomela J(2013)Survey of local algorithmsACM Computing Surveys10.1145/2431211.243122345:2(1-40)Online publication date: 12-Mar-2013
https://dl.acm.org/doi/10.1145/2431211.2431223
Göös MHirvonen JSuomela JKowalski DPanconesi A(2012)Lower bounds for local approximationProceedings of the 2012 ACM symposium on Principles of distributed computing10.1145/2332432.2332465(175-184)Online publication date: 16-Jul-2012
https://dl.acm.org/doi/10.1145/2332432.2332465
Friedman RKogan A(2011)Deterministic dominating set construction in networks with bounded degreeProceedings of the 12th international conference on Distributed computing and networking10.5555/1946143.1946149(65-76)Online publication date: 2-Jan-2011
https://dl.acm.org/doi/10.5555/1946143.1946149
Zhang YChin FTing H(2010)Approximated distributed minimum vertex cover algorithms for bounded degree graphsProceedings of the 16th annual international conference on Computing and combinatorics10.5555/1886811.1886827(100-109)Online publication date: 19-Jul-2010
https://dl.acm.org/doi/10.5555/1886811.1886827
Suomela JRicha AGuerraoui R(2010)Distributed algorithms for edge dominating setsProceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing10.1145/1835698.1835783(365-374)Online publication date: 25-Jul-2010
https://dl.acm.org/doi/10.1145/1835698.1835783
Show More Cited By

View Options

View options

Figures

Tables

Media

View Table of Conten