Search

For a fixed finite family of graphs FF, the FF-Minor-Free Deletion problemtakes as input a graph G and an integer ℓℓ and asks whether there exists a set X⊆V(G)X⊆V(G) of size at most ℓℓ such that G−XG−X is FF-minor-free. For F={K2}F={K2} and F={K3}F={K3} this encodes VertexCover and FeedbackVertex Set respectively. When parameterized by thefeedback vertex number of G these two problems areknown to admit a polynomial kernelization. Such a polynomial kernelization alsoexists for any FF containing a planar graph but no forests. In this paper we show that FF-Minor-Free Deletion parameterizedby the feedback vertex number is MK[2]MK[2]-hard for F={P3}F={P3}. This rules out the existence of a polynomial kernel ssuming NP⊈coNP/polyNP⊈coNP/poly, and also gives evidence that the problem does not admit a polynomialTuring kernel. Our hardness result generalizes to any FF not containing a P3P3-subgraph-free graph, using as parameter the vertex-deletion distance totreewidth mintw(F)mintw(F), where mintw(F)mintw(F) denotes the minimum treewidth of the graphs in FF. For the other case, where FF contains a P3P3-subgraph-free graph, we present a polynomial Turing kernelization. Ourresults extend to FF-Subgraph-Free Deletion.

For a fixed finite family of graphs FF, the FF-Minor-Free Deletion problemtakes as input a graph G and an integer ℓℓ and asks whether there exists a set X⊆V(G)X⊆V(G) of size at most ℓℓ such that G−XG−X is FF-minor-free. For F={K2}F={K2} and F={K3}F={K3} this encodes VertexCover and FeedbackVertex Set respectively. When parameterized by thefeedback vertex number of G these two problems areknown to admit a polynomial kernelization. Such a polynomial kernelization alsoexists for any FF containing a planar graph but no forests.In this paper we show that FF-Minor-Free Deletion parameterizedby the feedback vertex number is MK[2]MK[2]-hard for F={P3}F={P3}. This rules out the existence of a polynomial kernel ssuming NP⊈coNP/polyNP⊈coNP/poly, and also gives evidence that the problem does not admit a polynomialTuring kernel. Our hardness result generalizes to any FF not containing a P3P3-subgraph-free graph, using as parameter the vertex-deletion distance totreewidth mintw(F)mintw(F), where mintw(F)mintw(F) denotes the minimum treewidth of the graphs in FF. For the other case, where FF contains a P3P3-subgraph-free graph, we present a polynomial Turing kernelization. Ourresults extend to FF-Subgraph-Free Deletion.