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_0: We study the recently introduced Connected Feedback Vertex Set (CFVS) problem from the view-point of parameterized algorithms. CFVS is the connected variant of the classical Feedback Vertex Set problem and is defined as follows: given a graph G=(V,E) and an integer k, decide whether there exists F?V, |F|?k, such that G[V?F] is a forest and G[F] is connected. We show that Connected Feedback Vertex Set can be solved in time O(2 O(k) n O(1)) on general graphs and in time @math on graphs excluding a fixed graph H as a minor. Our result on general undirected graphs uses, as a subroutine, a parameterized algorithm for Group Steiner Tree, a well studied variant of Steiner Tree. We find the algorithm for Group Steiner Tree of independent interest and believe that it could be useful for obtaining parameterized algorithms for other connectivity problems.
@cite_18: A graph is d-degenerate if every subgraph contains a vertex of degree at most d. For instance, planar graphs are 5-degenerate. Inspired by the recent work by Philip, Raman and Sikdar, who have shown the existence of a polynomial kernel for Dominating Set in d-degenerate graphs, we investigate the kernelization complexity of problems that include a connectivity requirement in this class of graphs. Our main contribution is the proof that Connected Dominating Set does not admit a polynomial kernel in d-degenerate graphs for d>=2 unless [email protected]?coNP poly, which is known to cause a collapse of the polynomial hierarchy to its third level. We prove this using a problem that originates from bioinformatics-Colourful Graph Motif-analysed and proved to be NP-hard by This problem nicely encapsulates the hardness of the connectivity requirement in kernelization. Our technique also yields an alternative proof that, under the same complexity assumption, Steiner Tree does not admit a polynomial kernel. The original proof, via a reduction from Set Cover, is due to Dom, Lokshtanov and Saurabh. We extend our analysis by showing that, unless [email protected]?coNP poly, there do not exist polynomial kernels for Steiner Tree, Connected Feedback Vertex Set and Connected Odd Cycle Transversal in d-degenerate graphs for d>=2. On the other hand, we show a polynomial kernel for Connected Vertex Cover in graphs that do not contain the biclique K"i","j as a subgraph. As a d-degenerate graph cannot contain K"d"+"1","d"+"1 as a subgraph, the results holds also for graphs of bounded degeneracy.
@cite_1: For the vast majority of local graph problems standard dynamic programming techniques give c^tw V^O(1) algorithms, where tw is the treewidth of the input graph. On the other hand, for problems with a global requirement (usually connectivity) the best-known algorithms were naive dynamic programming schemes running in tw^O(tw) V^O(1) time. We breach this gap by introducing a technique we dubbed Cut&Count that allows to produce c^tw V^O(1) Monte Carlo algorithms for most connectivity-type problems, including Hamiltonian Path, Feedback Vertex Set and Connected Dominating Set, consequently answering the question raised by Lokshtanov, Marx and Saurabh [SODA'11] in a surprising way. We also show that (under reasonable complexity assumptions) the gap cannot be breached for some problems for which Cut&Count does not work, like CYCLE PACKING. The constant c we obtain is in all cases small (at most 4 for undirected problems and at most 6 for directed ones), and in several cases we are able to show that improving those constants would cause the Strong Exponential Time Hypothesis to fail. Our results have numerous consequences in various fields, like FPT algorithms, exact and approximate algorithms on planar and H-minor-free graphs and algorithms on graphs of bounded degree. In all these fields we are able to improve the best-known results for some problems.
@cite_12: 
Grigoriev and Sitters @cite_12 proved that Connected Feedback Vertex Set is -complete for planar graphs with maximum degree 9. Besides this result not much is known on the computational complexity of this problem except that it is fixed parameter tractable when parameterized by @math @cite_0 . The Connected Odd Cycle Transversal has been mainly studied from parameterized point of view @cite_1 @cite_18 . It is implicit in these works that Connected Odd Cycle Transversal is -complete, though we were not able to find any proof of this (simple) result. For the sake of completeness, we note now that it is implied by the stronger results we present in Theorems and .