Summary: The \(\mathcal {F}\)-Minor-Free Deletion problem asks, for a fixed set \(\mathcal {F}\) and an input consisting of a graph \(G\) and integer \(k\), whether \(k\) vertices can be removed from \(G\) such that the resulting graph does not contain any member of \(\mathcal {F} \) as a minor. F. V. Fomin et al. [“Planar \(\mathcal {F}\)-deletion: approximation, kernelization and optimal FPT algorithms”, in: Proceedings of the 53rd annual IEEE symposium on foundations of computer science, FOCS’12. Los Alamitos, CA: IEEE Computer Society. 470–479 (2012; doi:10.1109/FOCS.2012.62)] showed that the special case when \(\mathcal {F} \) contains at least one planar graph has a kernel of size \(f(\mathcal {F}) {\cdot} k^{g(\mathcal {F})}\) for some functions \(f\) and \(g\). They left open whether this Planar \(\mathcal {F}\)-Minor-Free Deletion problem has kernels whose size is uniformly polynomial, of the form \(f(\mathcal {F}) {\cdot} k^c\) for some universal constant \(c\). We prove that some Planar \(\mathcal {F}\)-Minor-Free Deletion problems do not have uniformly polynomial kernels (unless \(\mathrm{NP} \subseteq \mathrm{coNP/poly}\)), not even when parameterized by the vertex cover number. On the positive side, we consider the problem of determining whether \(k\) vertices can be removed to obtain a graph of treedepth at most \({\eta} \). We prove that this problem admits uniformly polynomial kernels with \({\mathcal {O}}(k^6)\) vertices for every fixed \({\eta} \).
For the entire collection see [Zbl 1316.68014].