KAIST Discrete Math Seminar

Let H be a planar graph. By a classical result of Robertson and Seymour, there is a function f(k) such that for all k and all graphs G, either G contains k vertex-disjoint subgraphs each containing H as a minor, or there is a subset X of at most f(k) vertices such that G−X has no H-minor. We prove that this remains true with f(k)=ck log k for some constant c depending on H. This bound is best possible, up to the value of c, and improves upon a recent bound of Chekuri and Chuzhoy. The proof is constructive and yields the first polynomial-time O(log ???)-approximation algorithm for packing subgraphs containing an H-minor.

This is joint work with Wouter Cames van Batenburg, Gwenaël Joret, and Jean-Florent Raymond.