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-2 | Engels |
---|---|
Pagina's (van-tot) | 192-214 |
Aantal pagina's | 23 |
Tijdschrift | Discrete Applied Mathematics |
Volume | 346 |
DOI's | |
Status | Gepubliceerd - 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).
Financiers | Financiernummer |
---|---|
European Union’s Horizon Europe research and innovation programme | |
European Research Council | |
European Union’s Horizon Europe research and innovation programme | 803421 |