On 26.02.2015 as a part of our 
Foundation for Polish Science Algorithmic Miniworkshop series we will have a seminar by Archontia Giannopoulou. The title of the talk is “Uniform Kernelization Complexity of Hitting Forbidden Minors” and the abstract is given below.
We plan to have a group discussion and joint lunch after his talk.
Abstract:
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. It generalizes classic graph problems such as Vertex Cover and Feedback Vertex Set. Fomin et al. (FOCS 2012) showed that the special case Planar-F-Minor-Free Deletion (when F contains at least one planar graph) has a kernel of polynomial size: instances (G,k) can efficiently be reduced to equivalent instances (G’,k) 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-Minor-Free 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.
In this talk we discuss to what extent provably effective and efficient preprocessing is possible for F-Minor-Free Deletion. In particular, we show that not all Planar-F-Minor-Free Deletion problems admit uniformly polynomial kernels but also that there exist problems that do admit uniformly polynomial kernels.
In this talk we discuss to what extent provably effective and efficient preprocessing is possible for F-Minor-Free Deletion. In particular, we show that not all Planar-F-Minor-Free Deletion problems admit uniformly polynomial kernels but also that there exist problems that do admit uniformly polynomial kernels.