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. Fomin et al. (FOCS 2012) showed that the special case when F contains at least one planar graph has a kernel of size f(F)-k~(g(F)) for some functions f and g. They left open whether this Planar F-Minor-Free Deletion problem has kernels whose size is uniformly polynomial, of the form f(F) · k~c for some universal constant c. We prove that some Planar F-Minor-Free Deletion problems do not have uniformly polynomial kernels (unless NP is contained in 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 η. We prove that this problem admits uniformly polynomial kernels with O(k~6) vertices for every fixed η.
展开▼
