We perform a systematic study in the computational complexity of the connected variant of three related transversal problems: Vertex Cover, Feedback Vertex Set, and Odd Cycle Transversal. Just like their original counterparts, these variants are NP-complete for general graphs. A graph @math is @math -free for some graph @math if @math contains no induced subgraph isomorphic to @math . It is known that Connected Vertex Cover is NP-complete even for @math -free graphs if @math contains a claw or a cycle. We show that the two other connected variants also remain NP-complete if @math contains a cycle or claw. In the remaining case @math is a linear forest. We show that Connected Vertex Cover, Connected Feedback Vertex Set, and Connected Odd Cycle Transversal are polynomial-time solvable for @math -free graphs for every constant @math . For proving these results we use known results on the price of connectivity for vertex cover, feedback vertex set, and odd cycle transversal. This is the first application of the price of connectivity that results in polynomial-time algorithms.
@cite_30: Abstract We continue the study of boundary classes for NP -hard problems and focus on seven NP -hard graph problems involving non-local properties: Hamiltonian Cycle , Hamiltonian Cycle Through Specified Edge , Hamiltonian Path , Feedback Vertex Set , Connected Vertex Cover , Connected Dominating Set and Graph VC CON Dimension . Our main result is the determination of the first boundary class for Feedback Vertex Set . We also determine boundary classes for Hamiltonian Cycle Through Specified Edge and Hamiltonian Path and give some insights on the structure of some boundary classes for the remaining problems.
@cite_26: 
@cite_3: An optimum rectilinear Steiner tree for a set A of points in the plane is a tree which interconnects A using horizontal and vertical lines of shortest possible total length. Such trees correspond to single net wiring patterns on printed backplanes which minimize total wire length. We show that the problem of determining this minimum length, given A, is NP-complete. Thus the problem of finding optimum rectilinear Steiner trees is probably computationally hopeless, and the emphasis of the literature for this problem on heuristics and special case algorithms is well justified. A number of intermediary lemmas concerning the NP-completeness of certain graph-theoretic problems are proved and may be of independent interest.
@cite_2: 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). Finally, dealing with hypergraphs, we study the complexity and the approximability of two natural generalizations.
@cite_5: This paper shows that both the nonseparating independent set problem and feedback set problem can be solved in polynomial time for graphs with no vertex degree exceeding 3 by reducing the problems to the matroid parity problem.
@cite_15: Discusses time complexity analysis of the minimum vertex cover and minimum connected vertex cover problems for 3-connected graphs. A vertex cover of a graph G=(V, E) is a subset N of V such that each element of E is incident upon some element of N, where V and E are the sets of vertices and of edges of G, respectively. A connected vertex cover of a graph G is a vertex cover of G such that the subgraph G(N) induced by N of G is connected. The minimum vertex cover problem (VCP) is the problem of finding a vertex cover of minimum cardinality, and the minimum connected vertex cover problem is similarly defined. >
@cite_25: We consider the concepts of a t-total vertex cover and a t-total edge cover(t>=1), which generalise the notions of a vertex cover and an edge cover, respectively. A t-total vertex (respectively edge) cover of a connected graph G is a vertex (edge) cover S of G such that each connected component of the subgraph of G induced by S has at least t vertices (edges). These definitions are motivated by combining the concepts of clustering and covering in graphs. Moreover they yield a spectrum of parameters that essentially range from a vertex cover to a connected vertex cover (in the vertex case) and from an edge cover to a spanning tree (in the edge case). For various values of t, we present NP-completeness and approximability results (both upper and lower bounds) and FPT algorithms for problems concerned with finding the minimum size of a t-total vertex cover, t-total edge cover and connected vertex cover, in particular improving on a previous FPT algorithm for the latter problem.
Already in the seventies, Garey and Johnson @cite_3 proved that Connected Vertex Cover is -complete even for planar graphs of maximum degree 4. Later, Priyadarsini and Hemalatha @cite_26 strengthened this result to 2-connected planar graphs of maximum degree 4, and Fernau and Manlove @cite_25 strengthened it to planar bipartite graphs of maximum degree 4. Wanatabe, Kajita, and Onaga @cite_15 proved -completeness of Connected Vertex Cover for 3-connected graphs. More recently, Munaro @cite_30 established -completeness of Connected Vertex Cover for line graphs of planar cubic bipartite graphs and for planar bipartite graphs of arbitrarily large girth. Ueno, Kajitani, and Gotoh @cite_5 proved that Connected Vertex Cover can be solved in polynomial time for graphs of maximum degree at most 3 and for trees. Escoffier, Gourv es, and Monnot @cite_2 improved the latter result by showing that Connected Vertex Cover is polynomial-time solvable for chordal graphs. It is known that Vertex Cover is polynomial-time solvable for chordal graphs as well. The same authors proposed to study the complexity of Connected Vertex Cover for other graph classes for which Vertex Cover is polynomial-time solvable.