Stable-ΠΠ partitions of graphs

For a set of graphs ΠΠ, the Stable-ΠΠ problem asks whether, given a graph GG, we can find an independent set SS in GG, such that G−S∈ΠG−S∈Π. For instance, if ΠΠ is the set of all bipartite graphs, Stable-ΠΠ coincides with vertex 3-colourability, and if ΠΠ is the set of 1-regular graphs, the problem is known as efficient edge domination. Numerous other examples of the Stable-ΠΠ problem have been studied in the literature. In the present contribution, we systematically study the Stable-ΠΠ problem with respect to the speed (a term meaning size) of ΠΠ. In particular, we show that for all hereditary classes ΠΠ with a subfactorial speed of growth, Stable-ΠΠ is solvable in polynomial time. We then explore the problem for minimal hereditary factorial classes ΠΠ. Contrary to the conjecture proposed in Lozin (2005)  [18], the complexity of Stable-ΠΠ turns out to be polynomial for nearly all minimal hereditary factorial classes ΠΠ. On the other hand, if we do not require ΠΠ to be hereditary, the complexity of the problem can jump to NP-completeness.