FOCS Conference 2024 Conference Paper
Obstructions to Erdös-Pósa Dualities for Minors
- Christophe Paul
- Evangelos Protopapas
- Dimitrios M. Thilikos
- Sebastian Wiederrecht
Let $\mathcal{G}$ and $\mathcal{H}$ be minor-closed graph classes. We say that the pair $(\mathcal{H}, \ \mathcal{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 \mathcal{G}$, either $G$ has $k$ pairwise vertex-disjoint sub graphs which do not belong to $\mathcal{H}$, or there exists a set $S\subseteq V(G)$ of size at most $f(k)$ for which $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 all graph classes $\mathcal{G}$. A minor-closed graph 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. In this paper, we prove that for every minor-closed graph class $\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. We show that each class $\mathcal{G}$ in $\mathfrak{C}_{\mathcal{H}}$ can be described as the set of all minors of some, suitably defined, sequence of grid-like graphs $\langle{W}_{k}\rangle_{k\in \mathbb{N}}$. Moreover, each $\mathrm{W}_{k}$ admits a half-integral packing, i. e. , $k$ copies of some $H\not\in \mathcal{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(\mathcal{H})$ denote the maximum size of an obstruction to $\mathcal{H}$. For every minor-closed graph class $\mathcal{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 \mathcal{H}$ or outputs a set of at most $2^{k^{\overline{\mathcal{O}}_{h}(1)}}$ vertices whose deletion creates a graph in $\mathcal{H}$ in time $2^{2^{k^{\mathcal{O}_{h}(1)}}}\cdot\vert G\vert ^{4}\log\vert G\vert$. Moreover, as a consequence of our results, for every minor-closed class $\mathcal{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 $\mathcal{H}$ -treewidth and elimination distance to $\mathcal{H}$.