From FVS to Planar F-Deletion

We describe a randomized constant ratio approximation algorithm for the F-deletion problem, where we are given a family of graphs F and we are looking for the smallest subset of vertices whose deletion removes all minor models of graphs from F. In other words, if G is the input graph and S is a solution, then G-S contains no graph from F as a minor.

We use feedback vertex set as a case in point (where the family F consists of just the triangle) and describe how the ideas can be generalized. We introduce the notion of an alpha-cover, which is a generic property: once a graph admits an alpha-cover, the path to such an approximation algorithm is clear. We will briefly touch on the notion of lossless protrusions and fast protrusion replacement which enable us to preprocess the graph to the point where it admits an alpha-cover.