Search-Space Reduction via Essential Vertices

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

4 Downloads (Pure)

Samenvatting

We investigate preprocessing for vertex-subset problems on graphs. While the notion of kernelization, originating in parameterized complexity theory, is a formalization of provably effective preprocessing aimed at reducing the total instance size, our focus is on finding a nonempty vertex set that belongs to an optimal solution. This decreases the size of the remaining part of the solution which still has to be found, and therefore shrinks the search space of fixed-parameter tractable algorithms for parameterizations based on the solution size. We introduce the notion of a c-essential vertex as one that is contained in all - c approximate solutions. For several classic combinatorial problems such as Odd Cycle Transversal and Directed Feedback Vertex Set, we show that under mild conditions a polynomial-time preprocessing algorithm can find a subset of an optimal solution that contains all 2-essential vertices, by exploiting packing/covering duality. This leads to FPT algorithms to solve these problems where the exponential term in the running time depends only on the number of nonessential vertices in the solution.
Originele taal-2Engels
Pagina's (van-tot)2392-2415
Aantal pagina's24
TijdschriftSIAM Journal on Discrete Mathematics
Volume38
Nummer van het tijdschrift3
DOI's
StatusGepubliceerd - 2024

Financiering

This work was funded by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement 803421, ReduceSearch).

Vingerafdruk

Duik in de onderzoeksthema's van 'Search-Space Reduction via Essential Vertices'. Samen vormen ze een unieke vingerafdruk.

Citeer dit