A tight Erdos-Pósa function for planar minors
Wouter Cames van Batenburg, Tony Huyn, Gwenaël Joret, Jean‐Florent Raymond · arXiv (Cornell University) · 2019
Let H be a planar graph. By a classical result of Robertson and Seymour, there is a function f : N → R such that for all k ϵ N 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 = c(H). This bound is best possible, up to the value of c, and improves upon a recent result of Chekuri and Chuzhoy [STOC 2013], who established this with f(k) = ck logd k for some universal constant d. The proof is constructive and yields a polynomial-time O(log OPT)-approximation algorithm for packing subgraphs containing an H-minor.