Hitting forbidden minors: Approximation and Kernelization

Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, Geevarghese Philip & Saket Saurabh
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 obtain a number of algorithmic results on the F-Deletion problem when F contains a planar graph. We give - a linear vertex...