Induced Erdős--Pósa property for long holes, long thetas, and beyond

Abstract

The induced Erdős--Pósa property in graphs relates the maximum number of pairwise anti-adjacent copies of an object with the minimum number of neighborhoods required to hit all copies. In this paper, the objects we consider are long cycles and long thetas, both as induced minors. Let $C_t$ denote the cycle with $t$ vertices and let ${\Theta }_t$ be the graph consisting of three internally disjoint and anti-adjacent paths, each with $t$ internal vertices, connecting the same pair of distinct vertices. We show that for every fixed $t$, both $C_t$ and ${\Theta }_t$ have the induced Erdős--Pósa property with respect to the induced minor relation. More precisely, for every integer $k$ and every graph $G$, one of the following two outcomes occurs: (i) $G$ contains $k$ pairwise vertex-disjoint and anti-adjacent copies of $C_t$ (resp., ${\Theta }_t$) as induced minors, or (ii) there is a set $X\subseteq V(G)$ of size $\mathcal{O}(tk\log k)$ such that the set $N[X]$, consisting of $X$ and its neighbors, hits all $C_t$ (resp., all ${\Theta }_t$) induced minors in $G$. This resolves in a strong form a special case of a conjecture of Ahn, Gollin, Huynh, and Kwon [SODA 2025]. From these results we derive that graphs that exclude $k$ disjoint copies of ${\Theta }_t$ as an induced minor admit balanced separators consisting of the neighborhood of $\mathcal{O}(tk\log k)$ vertices. This in turn resolves a special case of a conjecture of Gartland and Lokshtanov and, combined with known techniques, yields a QPTAS for Maximum Weight Independent Set and a number of its generalizations.

35 pages, 6 figures