Single-exponential FPT algorithms for enumerating secluded F-free subgraphs and deleting to scattered graph classes

The celebrated notion of important separators bounds the number of small (S,T)-separators in a graph which are ‘farthest from S’ in a technical sense. In this paper, we introduce a generalization of this powerful algorithmic primitive, tailored to undirected graphs, that is phrased in terms of k-secluded vertex sets: sets with an open neighborhood of size at most k. In this terminology, the bound on important separators says that there are at most 4 ^k maximal k-secluded connected vertex sets C containing S but disjoint from T. We generalize this statement significantly: even when we demand that G[C] avoids a finite set F of forbidden induced subgraphs, the number of such maximal subgraphs is 2 ^O(k) and they can be enumerated efficiently. This enumeration algorithm allows us to give improved parameterized algorithms for CONNECTED k-SECLUDED F-FREE SUBGRAPH and for deleting into scattered graph classes.