  The F-Minor-Free Deletion problem asks, for a fixed set 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 F as a minor. This
paper analyzes to what extent provably effective and efficient preprocessing is
possible for F-Minor-Free Deletion. Fomin et al. (FOCS 2012) showed that the
special case Planar F-Deletion (when F contains at least one planar graph) has
a kernel of size f(F) * k^{g(F)} for some functions f and g. The degree g of
the polynomial grows very quickly; it is not even known to be computable. Fomin
et al. left open whether Planar F-Deletion has kernels whose size is uniformly
polynomial, i.e., of the form f(F) * k^c for some universal constant c that
does not depend on F. Our results in this paper are twofold. (1) We prove that
some Planar F-Deletion problems do not have uniformly polynomial kernels
(unless NP is in coNP/poly). In particular, we prove that Treewidth-Eta
Deletion does not have a kernel with O(k^{eta/4} - eps) vertices for any eps >
0, unless NP is in coNP/poly. In fact, we even prove the kernelization lower
bound for the larger parameter vertex cover number. This resolves an open
problem of Cygan et al. (IPEC 2011). It is a natural question whether further
restrictions on F lead to uniformly polynomial kernels. However, we prove that
even when F contains a path, the degree of the polynomial must, in general,
depend on the set F. (2) A canonical F-Minor-Free Deletion problem when F
contains a path is Treedepth-eta Deletion: can k vertices be removed to obtain
a graph of treedepth at most eta? We prove that Treedepth-eta Deletion admits
uniformly polynomial kernels with O(k^6) vertices for every fixed eta. In order
to develop the kernelization we prove several new results about the structure
of optimal treedepth-decompositions.
