Search

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.

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.

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.