Samenvatting
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.
Originele taal-2 | Engels |
---|---|
Artikelnummer | 103597 |
Aantal pagina's | 16 |
Tijdschrift | Journal of Computer and System Sciences |
Volume | 148 |
DOI's | |
Status | Gepubliceerd - mrt. 2025 |
Financiering
This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 803421, ReduceSearch). [Formula presented] This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 803421, ReduceSearch).
Financiers | Financiernummer |
---|---|
European Research Council | |
European Union’s Horizon Europe research and innovation programme | 803421 |