A coarse Erdős-Pósa theorem

An induced packing of cycles in a graph is a set of vertex-disjoint cycles with no edges between them. We generalise the classic Erdős-Pósa theorem to induced packings of cycles. More specifically, we show that there exists a function f (k) = O (k log k ) such that for every positive integer k, every graph G contains either an induced packing of k cycles or a set X of at most f (k ) vertices such that the closed neighbourhood of X intersects all cycles in G. Our proof is constructive and yields a polynomial-time algorithm finding either the induced packing of cycles or the set X. Furthermore, we show that for every positive integer d, if a graph G does not contain two cycles at distance more than d, then G contains sets X1, X2 ⊆ V (G ) with |X1| ≤ 12(d + 1) and |X2| ≤ 12 such that, after removing the ball of radius 2d around X1 or the ball of radius 3d around X2, the resulting graphs are forests.