A Turing kernelization dichotomy for structural parameterizations of F-minor-free deletion

DOI10.1007/978-3-030-30786-8_9MaRDI QIDQ2301538zbMATH OpenOpenAlexFDO

Authors Huib Donkers, Bart M. P. Jansen

Publication date 24 February 2020

Full work available at URL https://arxiv.org/abs/1906.05565

zbMATH Keywords

minor-free deletionstructural parameterizationsubgraph-free deletionTuring kernelization

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Abstract: For a fixed finite family of graphs $mathcalF$, the $mathcalF$-Minor-Free Deletion problem takes as input a graph $G$ and an integer $ell$ and asks whether there exists a set $XsubseteqV(G)$ of size at most $ell$ such that $G-X$ is $mathcalF$-minor-free. For $mathcalF=K_2$ and $mathcalF=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 $mathcalF$ containing a planar graph but no forests. In this paper we show that $mathcalF$-Minor-Free Deletion parameterized by the feedback vertex number is MK[2]-hard for $mathcalF=P_3$. This rules out the existence of a polynomial kernel assuming $NPsubseteqcoNP/poly$, and also gives evidence that the problem does not admit a polynomial Turing kernel. Our hardness result generalizes to any $mathcalF$ not containing a $P_3$-subgraph-free graph, using as parameter the vertex-deletion distance to treewidth $mintw(mathcalF)$, where $mintw(mathcalF)$ denotes the minimum treewidth of the graphs in $mathcalF$. For the other case, where $mathcalF$ contains a $P_3$-subgraph-free graph, we present a polynomial Turing kernelization. Our results extend to $mathcalF$-Subgraph-Free Deletion.

Recommendations

• A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
• Preprocessing subgraph and minor problems: when does a small vertex cover help?
• Hitting forbidden minors: approximation and kernelization

Cited in

(4)

• On some FPT problems without polynomial Turing compressions
• A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
• Preprocessing subgraph and minor problems: when does a small vertex cover help?
• Preprocessing subgraph and minor problems: When does a small vertex cover help?

This page was built for publication: A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F}\)-minor-free deletion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2301538)