Abstract
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 is 5/3-approximable in any class of graphs where the vertex cover problem is polynomial (in particular in bipartite graphs).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theor. Comput. Sci. 237(1-2), 123–134 (2000)
Arkin, E.M., Halldórsson, M.M., Hassin, R.: Approximating the tree and tour covers of a graph. Inf. Process. Lett. 47(6), 275–282 (1993)
Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation (Combinatorial Optimization Problems and Their Approximability Properties). Springer, Berlin (1999)
Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1), 153–180 (1994)
Bar-Yehuda, R., Even, S.: On approximating a vertex cover for planar graphs. In: STOC, pp. 303–309 (1982)
Bodlaender, H.L.: A partial -arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209(1-2), 1–45 (1998)
Brandstadt, A., Le, V.B., Spinrad, J.: Graph classes: a survey. Society for Industrial and Applied Mathematic, Philadelphia (1999)
Dawar, A., Grohe, M., Kreutzer, S., Schweikardt, N.: Approximation schemes for first-order definable optimisation problems. In: LICS, pp. 411–420 (2006)
Demaine, E.D., Hajiaghayi, M.T.: Bidimensionality: new connections between fpt algorithms and ptass. In: SODA, pp. 590–601 (2005)
Fernau, H., Manlove, D.: Vertex and edge covers with clustering properties: Complexity and algorithms. In: Algorithms and Complexity in Durham, pp. 69–84 (2006)
Fujito, T.: How to trim an mst: A 2-approximation algorithm for minimum cost tree cover. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 431–442. Springer, Heidelberg (2006)
Garey, M.R., Johnson, D.S.: The rectilinear steiner tree problem in NP complete. SIAM Journal of Applied Mathematics 32, 826–834 (1977)
Garey, M.R., Johnson, D.S.: Computer and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)
Guo, J., Niedermeier, R., Wernicke, S.: Parameterized complexity of generalized vertex cover problems. In: Dehne, F., López-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol. 3608, pp. 36–48. Springer, Heidelberg (2005)
Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2 − ε. In: IEEE Conference on Computational Complexity, pp. 379–386. IEEE Computer Society Press, Los Alamitos (2003)
Könemann, J., Konjevod, G., Parekh, O., Sinha, A.: Improved approximations for tour and tree covers. Algorithmica 38(3), 441–449 (2003)
Mölle, D., Richter, S., Rossmanith, P.: Enumerate and expand: Improved algorithms for connected vertex cover and tree cover. In: Grigoriev, D., Harrison, J., Hirsch, E.A. (eds.) CSR 2006. LNCS, vol. 3967, pp. 270–280. Springer, Heidelberg (2006)
Mölle, D., Richter, S., Rossmanith, P.: Enumerate and expand: New runtime bounds for vertex cover variants. In: Chen, D.Z., Lee, D.T. (eds.) COCOON 2006. LNCS, vol. 4112, pp. 265–273. Springer, Heidelberg (2006)
Moser, H.: Exact algorithms for generalizations of vertex cover. Master’s thesis, Institut für Informatik, Friedrich-Schiller-Universität Jena (2005)
Savage, C.D.: Depth-first search and the vertex cover problem. Inf. Process. Lett. 14(5), 233–237 (1982)
Ueno, S., Kajitani, Y., Gotoh, S.: On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three. Discrete Mathematics 72, 355–360 (1988)
Wanatabe, T., Kajita, S., Onaga, K.: Vertex covers and connected vertex covers in 3-connected graphs. In: IEEE International Sympoisum on Circuits and Systems, pp. 1017–1020. IEEE Computer Society Press, Los Alamitos (1991)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Escoffier, B., Gourvès, L., Monnot, J. (2007). Complexity and Approximation Results for the Connected Vertex Cover Problem. In: Brandstädt, A., Kratsch, D., Müller, H. (eds) Graph-Theoretic Concepts in Computer Science. WG 2007. Lecture Notes in Computer Science, vol 4769. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74839-7_20
Download citation
DOI: https://doi.org/10.1007/978-3-540-74839-7_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74838-0
Online ISBN: 978-3-540-74839-7
eBook Packages: Computer ScienceComputer Science (R0)