Search

For a fixed finite family of graphs F , the F -Minor-Free Deletion problem takes as input a graph G and integer ℓ and asks whether a size- ℓ vertex set X exists such that G − X is F -minor-free. { K 2 } -Minor-Free Deletion and { K 3 } -Minor-Free Deletion encode Vertex Cover and Feedback Vertex Set respectively. When parameterized by the feedback vertex number of G these two problems are known to admit a polynomial kernelization. We show { P 3 } -Minor-Free Deletion parameterized by the feedback vertex number is MK [ 2 ] -hard. This rules out the existence of a polynomial kernel assuming NP ⊈ coNP / poly. Our hardness result generalizes to any F containing only graphs with a connected component of at least 3 vertices, using as parameter the vertex-deletion distance to treewidth min ⁡ tw (F) , where min ⁡ tw (F) denotes the minimum treewidth of the graphs in F. For all other families F we present a polynomial Turing kernelization. Our results extend to F -Subgraph-Free Deletion. [ABSTRACT FROM AUTHOR]