HITTING FORBIDDEN MINORS: APPROXIMATION AND KERNELIZATION.

We study a general class of problems called F-DELETION problems. In an 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 study the problem parameterized by k, using p-F-DELETION to refer to the parameterized version of the problem. We obtain a number of algorithmic results on the p-F-DELETION problem when F contains a planar graph. We give a linear vertex kernel on graphs excluding t-claw K_1,t, the star with t leaves, as an induced subgraph, where t is a fixed integer and 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 nontrivial application of protrusion techniques, previously used only for problems on topological graph classes. [ABSTRACT FROM AUTHOR]