A Turing kernelization dichotomy for structural parameterizations of F-Minor-Free Deletion

摘要

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. {K2}-Minor-Free Deletion and {K3}-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 {P3}-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.