A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion (Q2662677)

This paper is concerned with the notion of Turing kernelization, as applied to the \(F\)-minor-free deletion (FMFD) problem. In the FMFD problem we are given a graph \(G\), an integer \(l\) (which is the parameter), and a fixed finite family \(F\), and are asked if by deleting \(l\) or fewer vertices, we can make \(G\) \(F\)-minor free. The FMFD problem captures a number of optimization problems in graph theory. For instance, it is not hard to see that when \(F=P_2\) the problem is the minimum vertex cover problem and when \(F=P_3\) the problem is the minimum feedback vertex set problem. Turing kernelization was introduced by \textit{D. Hermelin} et al. [Algorithmica 71, No. 3, 702--730 (2015; Zbl 1312.68102)]. Turing kernelization generalizes the notion of Turing reductions. For instance, in a Turing reduction we can make use of multiple calls to an oracle, whereas in the traditional Karp reduction, only a single call can be made. In a Turing kernelization of size \(f\), for problem \(Q\), the algorithm can query an oracle to obtain an answer to any instance of problem \(Q\) of size \(|x|\) and parameter bounded by \(f(k)\) in a single step, and using the answer can adaptively solve any instance \((x,k)\) in time polynomial in \(|x|+k\). The paper descibes a neat dichotomy based on the structure of \(F\). In particular, it is shown that the \(P_3\)-minor-free deletion problem parameterized by the feedback vertex number is MK[2]-complete; this essentially rules out the existence of a polynomial kernel unless \(\mathrm{NP} \subseteq \mathrm{coNP/poly}\). On the other hand, when \(F\) contains a graph with no connected component of more than 2 vertices, the authors provide a polynomial-time kernelization. The paper contains several other results on this topic. It is extremely well-written and thorough with the casual reader in mind. All the terms used in the paper are clearly defined in the Preliminaries section. Moreover, reductions are illustrated with appropriate figures to clarify the exposition. Overall, this paper represents significant contributions which are presented appropriately.