Erdős-Pósa property for induced packings of long $S$-cycles

Abstract

The Erdős-Pósa theorem states that for every integer $k\ge 1$, every graph contains either $k$ vertex-disjoint cycles or a set of $\mathcal{O}(k\log k)$ vertices meeting all cycles. This fundamental min-max duality has been extended to numerous settings, including long cycles, $S$-cycles, that is, cycles containing a vertex in a prescribed set $S$, and cycles satisfying various additional constraints. In contrast, much less is known when the packing itself is required to be induced, namely, when distinct cycles are vertex-disjoint and have no edges between them. We prove that long $S$-cycles admit an induced version of the Erdős-Pósa-type duality. More precisely, we show that there exists a polynomial function $f(k,\ell )$ such that for all integers $k\ge 1$ and $\ell \ge 3$, every graph contains either an induced packing of $k$ $S$-cycles of length at least $\ell$ or a set of at most $f(k,\ell )$ vertices whose closed neighbourhood intersects all $S$-cycles of length at least $\ell$. The proof introduces a new ear-decomposition technique based on fragile ears and yields a polynomial-time algorithm for every fixed $\ell$.

50 pages and 2 figures