A coarse Erdos-P\'osa 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 Erdos-P\'osa theorem to induced packings of cycles. More specifically, we show that there exists a function f (k) = O (k 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 X₁, X₂ V (G) with X₁ 12 (d+1) and X₂ 12 such that after removing the ball of radius 2d around X₁ or the ball of radius 3d around X₂, the resulting graphs are forests. As a corollary, we prove that every graph with no K₁, ₓ induced subgraph and no induced packing of k cycles has tree-independence number at most O (tk k), and one can construct a corresponding tree-decomposition in polynomial time. This resolves a special case of a conjecture of Dallard et al. (arXiv: 2402. 11222), and implies that on such graphs, many NP-hard problems, such as Maximum Weight Independent Set, Maximum Weight Induced Matching, Graph Homomorphism, and Minimum Weight Feedback Vertex Set, are solvable in polynomial time. On the other hand, we show that the class of all graphs with no K₁, ₃ induced subgraph and no two cycles at distance more than 2 has unbounded tree-independence number.