Hitting Forbidden Minors: Approximation and Kernelization

Abstract

We study a general class of problems called $\mathcal{F}$-Deletion problems. In an $\mathcal{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 ${\cal F}$ of forbidden minors. We study the problem parameterized by $k$, using $p$-$\mathcal{F}$-Deletion to refer to the parameterized version of the problem. We obtain a number of algorithmic results on the $p$-$\mathcal{F}$-Deletion problem when $\mathcal{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 $\cal F$ only contains graph $\theta_c$ as a minor for a fixed integer $c$. The graph $\theta_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.