We study a general class of problems called p-F-Deletion problems. In an p-F-Deletion problem, we are asked whether a subset of at most k vertices can be deleted from a graph G such that the resulting graph does not contain as a minor any graph from the family F of forbidden minors. We obtain a number of algorithmic results on the p-F-Deletion problem when F contains a planar graph. We give 1. a linear vertex kernel on graphs excluding t-claw K1,t , the star with t leves, as an induced subgraph, where t is a fixed integer. 2. an approximation algorithm achieving an approximation ratio of O(log^3/2 OPT ), where OPT is the size of an optimal solution on general undirected graphs. Finally, we obtain polynomial kernels for the case when F only contains graph Θ_c as a minor for a fixed integer c. The graph Θ_c consists of two vertices connected by c parallel edges. Even though this may appear to be a very restricted class of problems it already encompasses well-studied problems such as Vertex Cover, Feedback Vertex Set and Diamond Hitting Set. The generic kernelization algorithm is based on a non-trivial application of protrusion techniques, previously used only for problems on topological graph classes.
In the CONNECTED DOMINATING SET problem we are given as input a graph G and a positive integer k, and are asked if there is a set S of at most k vertices of G such that S is a dominating set of G and the subgraph induced by S is connected. This is a basic connectivity problem that is known to be NP-complete, and it has been extensively studied using several algorithmic approaches. In this paper we study the effect of excluding short cycles, as a subgraph, on the kernelization complexity of CONNECTED DOMINATING SET. Kernelization algorithms are polynomial-time algorithms that take an input and a positive integer k (the parameter) and output an equivalent instance where the size of the new instance and the new parameter are both bounded by some function g(k). The new instance is called a g(k) kernel for the problem. If g(k) is a polynomial then we say that the problem admits polynomial kernels. The girth of a graph G is the length of a shortest cycle in G. It turns out that CONNECTED DOMINATING SET is ”hard” on graphs with small cycles, and becomes progressively easier as the girth increases. More specifically, we obtain the following interesting trichotomy: CONNECTED DOMINATING SET • does not have a kernel of any size on graphs of girth 3 or 4 (since the problem is W[2]-hard); • admits a g(k) kernel, where g(k) is roughly kO(k) , on graphs of girth 5 or 6 but has no polynomial kernel (unless the Polynomial Hierarchy (PH) collapses to the third level) on these graphs; • has a cubic (O(k3)) kernel on graphs of girth at least 7. While there is a large and growing collection of parameterized complexity results available for problems on graph classes characterized by excluded minors, our results add to the very few known in the field for graph classes characterized by excluded subgraphs.
The pathwidth of a graph is a measure of how path-like the graph is. Given a graph G and an integer k, the problem of finding whether there exist at most k vertices in G whose deletion results in a graph of pathwidth at most one is NP- complete. We initiate the study of the parameterized complexity of this problem, parameterized by k. We show that the problem has a quartic vertex-kernel: We show that, given an input instance (G = (V, E), k) where |V| = n, we can construct, in polynomial time, an instance (G', k') such that (i) (G, k) is a YES instance if and only if (G', k') is a YES instance, (ii) G has O(k^4) vertices, and (iii) k' ≤ k. We also give a fixed parameter tractable (FPT) algorithm for the problem that runs in O*(7^k · n^3) time. These figures compare favorably with the best results known for the closely related, and extensively studied, Feedback Vertex Set problem.
The Colorful Motif problem asks if, given a vertex-colored graph G, there exists a subset S of vertices of G such that the graph induced by G on S is connected and contains every color in the graph exactly once. The problem is motivated by applications in computational biology and is also well-studied from the theoretical point of view. In particular, it is known to be NP-complete even on trees of maximum degree three [Fellows et al, ICALP 2007]. In their pioneering paper that introduced the color-coding technique, Alon et al. [STOC 1995] show, inter alia, that the problem is FPT on general graphs. More recently, Cygan et al. [WG 2010] showed that Colorful Motif is NP-complete on comb graphs, a special subclass of the set of trees of maximum degree three. They also showed that the problem is not likely to admit polynomial kernels on forests.We continue the study of the kernelization complexity of the Colorful Motif problem restricted to simple graph classes. Surprisingly, the infeasibility of polynomial kernelization persists even when the input is restricted to comb graphs. We demonstrate this by showing a simple but novel composition algorithm. Further, we show that the problem restricted to comb graphs admits polynomially many polynomial kernels. To our knowledge, there are very few examples of problems with many polynomial kernels known in the literature. We also show hardness of polynomial kernelization for certain variants of the problem on trees; this rules out a general class of approaches for showing many polynomial kernels for the problem restricted to trees. Finally, we show that the problem is unlikely to admit polynomial kernels on another simple graph class, namely the set of all graphs of diameter two. As an application of our results, we settle the classical complexity of Connected Dominating Set on graphs of diameter two — specifically, we show that it is NP-complete.
In this paper we obtain parameterized subexponential-time algorithms for p-Kemeny Aggregation (p-KAGG) — a problem in social choice theory — and for p-One-Sided Crossing Minimization (p-OSCM) – a problem in graph drawing. These algorithms run in time O*(2O(sqrt(k)logk)), where k is the parameter, and significantly improve the previous best algorithms with running times O∗(1.403k) and O∗(1.4656k), respectively. We also study natural “above-guarantee” versions of these problems and show them to be fixed parameter tractable. In fact, we show that the above-guarantee versions are equivalent to a weighted variant of p-Directed Feedback Arc Set. Our results for the above-guarantee version of p-KAGG reveal an interesting contrast. We show that when the number of “votes” in the input to p-KAGG is odd the above guarantee version can still be solved in time O*(2O(sqrt(k)logk)), while if it is even then the problem cannot have a subexponential time algorithm unless the exponential time hypothesis fails (equivalently, unless FPT=M[1]).
We investigate the effect of certain natural connectivity constraints on the parameterized complexity of two fundamental graph covering problems, namely k-VERTEX COVER and k-EDGE COVER. Specifically, we impose the additional requirement that each connected component of a solution have at least t vertices (resp. edges from the solution), and call the problem t-TOTAL VERTEX COVER (resp. t- TOTAL EDGE COVER ). We show that – both problems remain fixed-parameter tractable with these restrictions, with running times of the form O∗(ck) for some constant c > 0 in each case; – for every t ≥ 2, t-TOTAL VERTEX COVER has no polynomial kernel unless the Polynomial Hierarchy collapses to the third level; – for every t ≥ 2, t-TOTAL EDGE COVER has a linear vertex kernel of size (t+1)k/t. These results significantly improve earlier work on these problems. Our no-poly-kernel result for t-TOTAL VERTEX COVER, and the known NP-hardness result for t-TOTAL EDGE COVER , are in stark contrast to the fact that k-VERTEX COVER has a 2k vertex kernel, and that k-EDGE COVER is solvable in polynomial time. This illustrates how even the slightest connectivity requirement results in a drastic change in the tractability of problems — the curse of connectivity!
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(2O(k) nO(1)) on general graphs and in time O(2O(sqrt(k) log k) nO(1)) 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 show that the k-Dominating Set problem is fixed-parameter tractable (FPT) and has a polynomial kernel for any class of graphs that exclude Ki,j as a subgraph, for any fixed i, j ≥ 1. This strictly includes every class of graphs for which this problem has been previously shown to have FPT algorithms and/or polynomial kernels. In particular, our result implies that the problem restricted to bounded-degenerate graphs has a polynomial kernel, solving an open problem posed by Alon and Gutner.