Preprocessing vertex-deletion problems: Characterizing graph properties by low-rank adjacencies

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

1 Citaat (Scopus)
146 Downloads (Pure)

Samenvatting

We consider the Π-FREE DELETION problem parameterized by the size of a vertex cover, for a range of graph properties Π. Given an input graph G, this problem asks whether there is a subset of at most k vertices whose removal ensures the resulting graph does not contain a graph from Π as an induced subgraph. We introduce the concept of characterizing a graph property Π by low-rank adjacencies, and use it as the cornerstone of a general kernelization theorem for Π-FREE DELETION parameterized by the size of a vertex cover. The resulting framework captures problems such as AT-FREE DELETION, WHEEL-FREE DELETION, and INTERVAL DELETION. Moreover, our new framework shows that the vertex-deletion problem to perfect graphs has a polynomial kernel when parameterized by vertex cover, thereby resolving an open question by Fomin et al. (2014) [18].

Originele taal-2Engels
Pagina's (van-tot)59-79
Aantal pagina's21
TijdschriftJournal of Computer and System Sciences
Volume126
DOI's
StatusGepubliceerd - jun. 2022

Bibliografische nota

Publisher Copyright:
© 2021 The Author(s)

Financiering

Funding: 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). Image 1 Image 2

Vingerafdruk

Duik in de onderzoeksthema's van 'Preprocessing vertex-deletion problems: Characterizing graph properties by low-rank adjacencies'. Samen vormen ze een unieke vingerafdruk.

Citeer dit