Obstructions to Erdös-Pósa Dualities for Minors

Let G and H be minor-closed graph classes. We say that the pair (H,G) is an Erdös-Pósa pair (EP-pair) if there exists a function f such that for every k and every graph G in G, either G has k pairwise vertex-disjoint sub graphs which do not belong to H, or there exists a set S subseteq V(G) of size at most f(k) for which G-S H. The classic result of Erdös and Pósa says that if F is the class of forests, then (F, G) is an EP-pair for all graph classes G. A minor-closed graph class G is an EP-counterexample for H if G is minimal with the property that (H,G) is not an EP-pair. In this paper, we prove that for every minor-closed graph class H the set C_H of all EP-counterexamples for H is finite. In particular, we provide a complete characterization of C_H for every H and give a constructive upper bound on its size. We show that each class G in C_H can be described as the set of all minors of some, suitably defined, sequence of grid-like graphs W_kk N. Moreover, each W_k admits a half-integral packing, i.e., k copies of some H\not\in H where no vertex is used more than twice. This implies a complete delineation of the half-integrality threshold of the Erdös-Pósa property for minors and as a corollary, we obtain a constructive proof of Thomas' conjecture on the half-integral Erdös-Pósa property for minors which was recently confirmed by Liu. Our results are algorithmic. Let H=h(H) denote the maximum size of an obstruction to H. For every minor-closed graph class H, we construct an algorithm that, given a graph G and an integer k, either outputs a half-integral packing of k copies of some H\not\in H or outputs a set of at most 2kO_H(1) vertices whose deletion creates a graph in H in time 2²kO_H(1)}·|G|⁴log|G|. Moreover, as a consequence of our results, for every minor-closed class H, we obtain min-max-dualities, which may be seen as analogues of the celebrated Grid Theorem of Robertson and Seymour, for the recently introduced parameters H-treewidth and elimination distance to H.