For a set of graphs $\Pi$, the STABLE-$\Pi$ problem asks whether a given graph $G$ has an independent set $S$ such that $G-S\in \Pi$. We systematically study the STABLE-$\Pi$ problem with respect to the speed (a term meaning size) of $\Pi$. We show that for all hereditary classes $\Pi$ with a subfactorial speed of growth, STABLE-$\Pi$ is solvable in polynomial time. We then study factorial hereditary classes. We show that, contrary to a conjecture proposed in the literature, the complexity of STABLE-$\Pi$ is polynomial for nearly all minimal factorial hereditary classes $\Pi$.
Joint work with Konrad Dabrowski and Vadim Lozin.