TY - GEN
T1 - Single-Exponential FPT Algorithms for Enumerating Secluded ℱ-Free Subgraphs and Deleting to Scattered Graph Classes.
AU - Jansen, Bart M. P.
AU - Kroon, Jari J. H. de
AU - Wlodarczyk, Michal
N1 - DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.
PY - 2023/12
Y1 - 2023/12
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 - http://www.scopus.com/inward/record.url?scp=85179130997&partnerID=8YFLogxK
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 - 1
EP - 18
BT - 34th International Symposium on Algorithms and Computation, ISAAC 2023
A2 - Iwata, Satoru
A2 - Iwata, Satoru
A2 - Kakimura, Naonori
PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik
ER -