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 l and asks whether there exists a set X {is contained in} V(G) of size at most C 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-hard for F = {P_3}. This rules out the existence of a polynomial kernel assuming NP {is not contained in} 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 min tw(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.