Back to Search
Start Over
A Turing kernelization dichotomy for structural parameterizations of ℱ -minor-free deletion
- Source :
- Graph-Theoretic Concepts in Computer Science-45th International Workshop, WG 2019, Revised Papers, 106-119, STARTPAGE=106;ENDPAGE=119;TITLE=Graph-Theoretic Concepts in Computer Science-45th International Workshop, WG 2019, Revised Papers
- Publication Year :
- 2019
- Publisher :
- Springer, 2019.
-
Abstract
- 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.
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- Graph-Theoretic Concepts in Computer Science-45th International Workshop, WG 2019, Revised Papers, 106-119, STARTPAGE=106;ENDPAGE=119;TITLE=Graph-Theoretic Concepts in Computer Science-45th International Workshop, WG 2019, Revised Papers
- Accession number :
- edsair.narcis........d281c0b1bb5ac4183821128a6004579e