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.
