Kernelization for feedback vertex set via elimination distance to a forest

David Dekker, Bart M.P. Jansen (Corresponding author)

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

2 Downloads (Pure)

Samenvatting

We study efficient preprocessing for the undirected FEEDBACK VERTEX SET problem, a fundamental problem in graph theory which asks for a minimum-sized vertex set whose removal yields an acyclic graph. More precisely, we aim to determine for which parameterizations this problem admits a polynomial kernel. While a characterization is known for the related VERTEX COVER problem based on the recently introduced notion of bridge-depth, it remained an open problem whether this could be generalized to FEEDBACK VERTEX SET. The answer turns out to be negative; the existence of polynomial kernels for structural parameterizations for FEEDBACK VERTEX SET is governed by the elimination distance to a forest. Under the standard assumption NP⁄⊆coNP/poly, we prove that for any minor-closed graph class G, FEEDBACK VERTEX SET parameterized by the size of a modulator to G has a polynomial kernel if and only if G has bounded elimination distance to a forest. This captures and generalizes all existing kernels for structural parameterizations of the FEEDBACK VERTEX SET problem.

Originele taal-2Engels
Pagina's (van-tot)192-214
Aantal pagina's23
TijdschriftDiscrete Applied Mathematics
Volume346
DOI's
StatusGepubliceerd - 31 mrt. 2024

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). 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 Union’s Horizon Europe research and innovation programme
European Research Council
European Union’s Horizon Europe research and innovation programme803421

    Vingerafdruk

    Duik in de onderzoeksthema's van 'Kernelization for feedback vertex set via elimination distance to a forest'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit