Abstract
The Connected Vertex Cover problem is to decide if a graph G has a vertex cover of size at most k that induces a connected subgraph of G. This is a well-studied problem, known to be NP-complete for restricted graph classes, and, in particular, for H-free graphs if H is not a linear forest. On the other hand, the problem is known to be polynomial-time solvable for \(sP_2\)-free graphs for any integer \(s\ge 1\). We prove that it is also polynomial-time solvable for \((sP_1+P_5)\)-free graphs for every integer \(s\ge ~0\).
This work was supported by The Leverhulme Trust (Grant RPG-2016-258).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bacsó, G., Tuza, Zs.: Dominating cliques in \(P_5\)-free graphs, Periodica Mathematica Hungarica 21, 303–308 (1990)
Balas, E., Yu, C.S.: On graphs with polynomially solvable maximum-weight clique problem. Networks 19, 247–253 (1989)
Camby, E., Cardinal, J., Fiorini, S., Schaudt, O.: The price of connectivity for vertex cover. Discret. Math. Theor. Comput. Sci. 16, 207–224 (2014)
Camby, E., Schaudt, O.: A new characterization of \(P_k\)-free graphs. Algorithmica 75, 205–217 (2016)
Cardinal, J., Levy, E.: Connected vertex covers in dense graphs. Theor. Comput. Sci. 411, 2581–2590 (2010)
Chiarelli, N., Hartinger, T.R., Johnson, M., Milanic, M., Paulusma, D.: Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity. Theor. Comput. Sci. 705, 75–83 (2018)
Escoffier, B., Gourvès, L., Monnot, J.: Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs. Theor. Comput. Sci. 8, 36–49 (2010)
Fernau, H., Manlove, D.: Vertex and edge covers with clustering properties: complexity and algorithms. J. Discret. Algorithms 7, 149–167 (2009)
Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32, 826–834 (1977)
Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Comb. Theory, Ser. B 16, 47–56 (1974)
Grzesik, A., Klimošová, T., Pilipczuk, M., Pilipczuk, M.: Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs. Manuscript (2017)
Hartinger, T.R., Johnson, M., Milanic, M., Paulusma, D.: The price of connectivity for transversals. Eur. J. Comb. 58, 203–224 (2016)
Li, Y., Yang, Z., Wang, W.: Complexity and algorithms for the connected vertex cover problem in 4-regular graphs. Appl. Math. Comput. 301, 107–114 (2017)
Lokshtanov, D., Vatshelle, M., Villanger, Y.: Independent set in \(P_5\)-free graphs in polynomial time. In: Proceedings of SODA 2014, pp. 570–581 (2014)
Minty, G.J.: On maximal independent sets of vertices in claw-free graphs. J. Comb. Theory, Ser. B 28, 284–304 (1980)
Munaro, A.: Boundary classes for graph problems involving non-local properties. Theor. Comput. Sci. 692, 46–71 (2017)
Poljak, S.: A note on stable sets and colorings of graphs. Commentationes Mathematicae Universitatis Carolinae 15, 307–309 (1974)
Priyadarsini, P.K., Hemalatha, T.: Connected vertex cover in 2-connected planar graph with maximum degree 4 is NP-complete. Int. J. Math. Phys. Eng. Sci. 2, 51–54 (2008)
Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6, 505–517 (1977)
Sbihi, N.: Algorithme de recherche d’un stable de cardinalité maximum dans un graphe sans étoile. Discret. Math. 29, 53–76 (1980)
Ueno, S., Kajitani, Y., Gotoh, S.: On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three. Discret. Math. 72, 355–360 (1988)
Wanatabe, T., Kajita, S., Onaga, K.: Vertex covers and connected vertex covers in 3-connected graphs. In: Proceedings of IEEE ISCAS 1991, pp. 1017–1020 (1991)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Johnson, M., Paesani, G., Paulusma, D. (2018). Connected Vertex Cover for \((sP_1+P_5)\)-Free Graphs. In: Brandstädt, A., Köhler, E., Meer, K. (eds) Graph-Theoretic Concepts in Computer Science. WG 2018. Lecture Notes in Computer Science(), vol 11159. Springer, Cham. https://doi.org/10.1007/978-3-030-00256-5_23
Download citation
DOI: https://doi.org/10.1007/978-3-030-00256-5_23
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-00255-8
Online ISBN: 978-3-030-00256-5
eBook Packages: Computer ScienceComputer Science (R0)