Single-Exponential FPT Algorithms for Enumerating Secluded ℱ-Free Subgraphs and Deleting to Scattered Graph Classes

09/20/2023
by   Bart M. P. Jansen, et al.
0

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 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 ℱ of forbidden induced subgraphs, the number of such maximal subgraphs is 2^O(k) and they can be enumerated efficiently. This allows us to make significant improvements for two problems from the literature. Our first application concerns the 'Connected k-Secluded ℱ-free subgraph' problem, where ℱ is a finite set of forbidden induced subgraphs. Given a graph in which each vertex has a positive integer weight, the problem asks to find a maximum-weight connected k-secluded vertex set C ⊆ V(G) such that G[C] does not contain an induced subgraph isomorphic to any F ∈ℱ. The parameterization by k is known to be solvable in triple-exponential time via the technique of recursive understanding, which we improve to single-exponential. Our second application concerns the deletion problem to scattered graph classes. Here, the task is to find a vertex set of size at most k whose removal yields a graph whose each connected component belongs to one of the prescribed graph classes Π_1, …, Π_d. We obtain a single-exponential algorithm whenever each class Π_i is characterized by a finite number of forbidden induced subgraphs. This generalizes and improves upon earlier results in the literature.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset