A Turing Kernelization Dichotomy for Structural Parameterizations of F-Minor-Free Deletion
share
For a fixed finite family of graphs F, the F-Minor-Free Deletion problem takes as input a graph G and an integer ℓ and asks whether there exists a set X ⊆ V(G) of size at most ℓ 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 mintw(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.
READ FULL TEXT