Single-exponential FPT algorithms for enumerating secluded F -free subgraphs and deleting to scattered graph classes
Bart M. P. Jansen, Jari J. H. de Kroon, Michał Włodarczyk · Journal of Computer and System Sciences · 2024
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.