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

Abstract

Let $\mathcal{G}$ and $\mathcal{H}$ be minor-closed graph classes. The pair $(\mathcal{H},\mathcal{G})$ is an Erdős-Pósa pair (EP-pair) if there is a function $f$ where, for every $k$ and every $G\in \mathcal{G},$ either $G$ has $k$ pairwise vertex-disjoint subgraphs not belonging to $\mathcal{H},$ or there is a set $S\subseteq V(G)$ where $|S|\le f(k)$ and $G-S\in \mathcal{H}.$ The classic result of Erdős and Pósa says that if $\mathcal{F}$ is the class of forests, then $(\mathcal{F},\mathcal{G})$ is an EP-pair for every $\mathcal{G}$. The class $\mathcal{G}$ is an EP-counterexample for $\mathcal{H}$ if $\mathcal{G}$ is minimal with the property that $(\mathcal{H},\mathcal{G})$ is not an EP-pair. We prove that for every $\mathcal{H}$ the set ${\mathfrak{C}}_{\mathcal{H}}$ of all EP-counterexamples for $\mathcal{H}$ is finite. In particular, we provide a complete characterization of ${\mathfrak{C}}_{\mathcal{H}}$ for every $\mathcal{H}$ and give a constructive upper bound on its size. Each class $\mathcal{G}\in {\mathfrak{C}}_{\mathcal{H}}$ can be described as all minors of a sequence of grid-like graphs $⟨{\mathcal{W}}_k{⟩}_{k\in \mathbb{N}}.$ Moreover, each ${\mathcal{W}}_k$ admits a half-integral packing: $k$ copies of some $H\notin \mathcal{H}$ where no vertex is used more than twice. This gives a complete delineation of the half-integrality threshold of the Erdős-Pósa property for minors and yields a constructive proof of Thomas' conjecture on the half-integral Erdős-Pósa property for minors (recently confirmed, non-constructively, by Liu). Let $h$ be the maximum size of a graph in $\mathcal{H}.$ For every class $\mathcal{H},$ we construct an algorithm that, given a graph $G$ and a $k,$ either outputs a half-integral packing of $k$ copies of some $H\notin \mathcal{H}$ or outputs a set of at most $2^{k_h^{\mathcal{O}}(1)}$ vertices whose deletion creates a graph in $\mathcal{H}$ in time $2^{2^{k^{{\mathcal{O}}_h(1)}}}\cdot |G{|}^4\log |G|.$

Accepted to FOCS 2024