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 an integer I and asks whether there exists a set X ⊆ V(G) of size at most I such that G — X is F-minor-free. For F = {K_2} and F = {K_3} this encodes 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. Such a polynomial kernelization also exists for any F containing a planar graph but no forests. In this paper we show that F-Minor-Free Deletion parameterized by the feedback vertex number is MK[2]-hard for F = {P_3}. This rules out the existence of a polynomial kernel assuming NP ⊄ coNP/poly, and also gives evidence that the problem does not admit a polynomial Turing kernel. Our hardness result generalizes to any F not containing a P_3-subgraph-free graph, using as parameter the vertex-deletion distance to treewidth mintw(F), where min tw(F) denotes the minimum treewidth of the graphs in F For the other case, where F contains a P_3-subgraph-free graph, we present a polynomial Turing kernelization. Our results extend to F-Subgraph-Free Deletion.