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.
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 .
@cite_0 @cite_18 @cite_1 @cite_12
2057355493 2007985221 2020889718 2592840164
A cycle transversal (or feedback vertex set) of a graph G is a subset T@?V(G) such that T@?V(C) 0@? for every cycle C of G. This work considers the problem of finding special cycle transversals in perfect graphs and cographs. We prove that finding a minimum cycle transversal T in a perfect graph G is NP-hard, even for bipartite graphs with maximum degree four. Since G-T is acyclic, this result implies that finding a maximum acyclic induced subgraph of a perfect graph is also NP-hard. Other special properties of T are considered. A clique (stable, respectively) cycle transversal, or simply cct (sct, respectively) is a cycle transversal which is a clique (stable set, respectively). Recognizing graphs which admit a cct can be done in polynomial time; however, no structural characterization of such graphs is known, even for perfect graphs. We characterize cographs with cct in terms of forbidden induced subgraphs and describe their structure. This leads to linear time recognition of cographs with cct. We also prove that deciding whether a perfect graph admits an sct is NP-complete. We characterize cographs with sct in terms of forbidden induced subgraphs; this characterization also leads to linear time recognition. 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. We investigate a generalization of the classical Feedback Vertex Set (FVS) problem from the point of view of parameterized algorithms. Independent Feedback Vertex Set (IFVS) is the ''independent'' variant of the FVS problem and is defined as follows: given a graph G and an integer k, decide whether there exists [email protected]?V(G), |F|@?k, such that G[V(G)@?F] is a forest and G[F] is an independent set; the parameter is k. Note that the similarly parameterized version of the FVS problem-where there is no restriction on the graph G[F]-has been extensively studied in the literature. The connected variant CFVS-where G[F] is required to be connected-has received some attention as well. The FVS problem easily reduces to the IFVS problem in a manner that preserves the solution size, and so any algorithmic result for IFVS directly carries over to FVS. We show that IFVS can be solved in O(5^kn^O^(^1^)) time, where n is the number of vertices in the input graph G, and obtain a cubic (O(k^3)) kernel for the problem. Note the contrast with the CFVS problem, which does not admit a polynomial kernel unless [email protected]?NP Poly. In this paper we study the "independent" version of the classic Feedback Vertex Set problem in the realm of parameterized algorithms and moderately exponential time algorithms. More precisely, we study the Independent Feedback Vertex Set problem, where we are given an undirected graph G on n vertices and a positive integer k, and the objective is to check if there is an independent feedback vertex set of size at most k. A set S subseteq V(G) is called an independent feedback vertex set (ifvs) if S is an independent set and G is a forest. In this paper we design two deterministic exact algorithms for Independent Feedback Vertex Set with running times O*(4.1481^k) and O*(1.5981^n). In fact, the algorithm with O*(1.5981^n) running time finds the smallest sized ifvs, if an ifvs exists. Both the algorithms are based on interesting measures and improve the best known algorithms for the problem in their respective domains. In particular, the algorithm with running time O*(4.1481^k) is an improvement over the previous algorithm that ran in time O*(5^k). On the other hand, the algorithm with running time O*(1.5981^n) is the first moderately exponential time algorithm that improves over the naive algorithm that enumerates all the subsets of V(G). Additionally, we show that the number of minimal ifvses in any graph on n vertices is upper bounded by 1.7485^n.