TY - GEN
T1 - Single-Exponential FPT Algorithms for Enumerating Secluded ℱ-Free Subgraphs and Deleting to Scattered Graph Classes
AU - Jansen, Bart M. P.
AU - de Kroon, Jari J.H.
AU - Włodarczyk, Michał
PY - 2023/11/28
Y1 - 2023/11/28
N2 - 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 make significant improvements for two problems from the literature. Our first application concerns the Connected k-Secluded F-free subgraph problem, where F 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 ∈ 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. A scattered graph class is defined by demanding that every connected component is contained in at least one of the prescribed graph classes Π1, . . ., Π
d. The deletion problem to a scattered graph class is to find a vertex set of size at most k whose removal yields a graph from the class. 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.
AB - 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 make significant improvements for two problems from the literature. Our first application concerns the Connected k-Secluded F-free subgraph problem, where F 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 ∈ 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. A scattered graph class is defined by demanding that every connected component is contained in at least one of the prescribed graph classes Π1, . . ., Π
d. The deletion problem to a scattered graph class is to find a vertex set of size at most k whose removal yields a graph from the class. 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.
KW - fixed-parameter tractability
KW - important separators
KW - secluded subgraphs
UR - https://www.scopus.com/pages/publications/85179130997
U2 - 10.4230/LIPIcs.ISAAC.2023.42
DO - 10.4230/LIPIcs.ISAAC.2023.42
M3 - Conference contribution
T3 - Leibniz International Proceedings in Informatics, (LIPIcs)
SP - 42:1-42:18
BT - 34th International Symposium on Algorithms and Computation (ISAAC 2023)
A2 - Iwata, Satoru
A2 - Kakimura, Naonori
PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik
T2 - 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Y2 - 3 December 2023 through 6 December 2023
ER -