A Turing kernelization dichotomy for structural parameterizations of F-Minor-Free Deletion
2021
For a fixed finite family of graphs , the problem takes as input a graph and integer and asks whether a size- vertex set exists such that is -minor-free. and encode and respectively. When parameterized by the feedback vertex number of these two problems are known to admit a polynomial kernelization. We show parameterized by the feedback vertex number is -hard. This rules out the existence of a polynomial kernel assuming . Our hardness result generalizes to any containing only graphs with a connected component of at least 3 vertices, using as parameter the vertex-deletion distance to treewidth , where denotes the minimum treewidth of the graphs in . For all other families we present a polynomial Turing kernelization. Our results extend to .
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI