Single-exponential FPT algorithms for enumerating secluded F-free subgraphs and deleting to scattered graph classes

Bart M.P. Jansen (Corresponding author), Jari J.H. de Kroon, Michal Wlodarczyk

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

2 Downloads (Pure)

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-2Engels
Artikelnummer103597
Aantal pagina's16
TijdschriftJournal of Computer and System Sciences
Volume148
DOI's
StatusGepubliceerd - 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).

FinanciersFinanciernummer
European Research Council
European Union’s Horizon Europe research and innovation programme803421

    Vingerafdruk

    Duik in de onderzoeksthema's van 'Single-exponential FPT algorithms for enumerating secluded F-free subgraphs and deleting to scattered graph classes'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit