Preprocessing to reduce the search space: Antler structures for feedback vertex set

Huib Donkers; Bart M.P. Jansen

doi:10.1016/J.JCSS.2024.103532

Preprocessing to reduce the search space: Antler structures for feedback vertex set

Huib Donkers, Bart M.P. Jansen (Corresponding author)

Research output: Contribution to journal › Article › Academic › peer-review

1 Citation (Scopus)

1 Downloads (Pure)

Abstract

The goal of this paper is to open up a new research direction aimed at understanding the power of preprocessing in speeding up algorithms that solve NP-hard problems exactly. We explore this direction for the classic Feedback Vertex Set problem on undirected graphs, leading to a new type of graph structure called antler decomposition, which identifies vertices that belong to an optimal solution. It is an analogue of the celebrated crown decomposition which has been used for Vertex Cover. We develop the graph structure theory around such decompositions and develop fixed-parameter tractable algorithms to find them, parameterized by the number of vertices for which they witness presence in an optimal solution. This reduces the search space of fixed-parameter tractable algorithms parameterized by the solution size that solve Feedback Vertex Set.

Original language	English
Article number	103532
Number of pages	26
Journal	Journal of Computer and System Sciences
Volume	144
DOIs	https://doi.org/10.1016/J.JCSS.2024.103532
Publication status	Published - Sept 2024

Funding

Related Version An extended abstract of this work appeared in the Proceedings of the 47th Workshop on Graph-Theoretical Concepts in Computer Science, WG 2021. Funding Bart M.P. Jansen: 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 Acknowledgements In memory of Rolf Niedermeier and his love for the art of problem parameterization. Funding Bart M.P. Jansen: 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]

Funders	Funder number
European Union's Horizon 2020 - Research and Innovation Framework Programme
H2020 European Research Council
European Union's Horizon 2020 - Research and Innovation Framework Programme	803421

Keywords

Feedback vertex set
Graph decomposition
Kernelization
Preprocessing

Access to Document

10.1016/J.JCSS.2024.103532Licence: CC BY

pdfFinal published version, 818 KBLicence: CC BY

Cite this

@article{8b525f23650640d8b646eab32fc82691,

title = "Preprocessing to reduce the search space: Antler structures for feedback vertex set",

abstract = "The goal of this paper is to open up a new research direction aimed at understanding the power of preprocessing in speeding up algorithms that solve NP-hard problems exactly. We explore this direction for the classic Feedback Vertex Set problem on undirected graphs, leading to a new type of graph structure called antler decomposition, which identifies vertices that belong to an optimal solution. It is an analogue of the celebrated crown decomposition which has been used for Vertex Cover. We develop the graph structure theory around such decompositions and develop fixed-parameter tractable algorithms to find them, parameterized by the number of vertices for which they witness presence in an optimal solution. This reduces the search space of fixed-parameter tractable algorithms parameterized by the solution size that solve Feedback Vertex Set.",

keywords = "Feedback vertex set, Graph decomposition, Kernelization, Preprocessing",

author = "Huib Donkers and Jansen, {Bart M.P.}",

year = "2024",

month = sep,

doi = "10.1016/J.JCSS.2024.103532",

language = "English",

volume = "144",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Preprocessing to reduce the search space

T2 - Antler structures for feedback vertex set

AU - Donkers, Huib

AU - Jansen, Bart M.P.

PY - 2024/9

Y1 - 2024/9

N2 - The goal of this paper is to open up a new research direction aimed at understanding the power of preprocessing in speeding up algorithms that solve NP-hard problems exactly. We explore this direction for the classic Feedback Vertex Set problem on undirected graphs, leading to a new type of graph structure called antler decomposition, which identifies vertices that belong to an optimal solution. It is an analogue of the celebrated crown decomposition which has been used for Vertex Cover. We develop the graph structure theory around such decompositions and develop fixed-parameter tractable algorithms to find them, parameterized by the number of vertices for which they witness presence in an optimal solution. This reduces the search space of fixed-parameter tractable algorithms parameterized by the solution size that solve Feedback Vertex Set.

AB - The goal of this paper is to open up a new research direction aimed at understanding the power of preprocessing in speeding up algorithms that solve NP-hard problems exactly. We explore this direction for the classic Feedback Vertex Set problem on undirected graphs, leading to a new type of graph structure called antler decomposition, which identifies vertices that belong to an optimal solution. It is an analogue of the celebrated crown decomposition which has been used for Vertex Cover. We develop the graph structure theory around such decompositions and develop fixed-parameter tractable algorithms to find them, parameterized by the number of vertices for which they witness presence in an optimal solution. This reduces the search space of fixed-parameter tractable algorithms parameterized by the solution size that solve Feedback Vertex Set.

KW - Feedback vertex set

KW - Graph decomposition

KW - Kernelization

KW - Preprocessing

UR - http://www.scopus.com/inward/record.url?scp=85189855206&partnerID=8YFLogxK

U2 - 10.1016/J.JCSS.2024.103532

DO - 10.1016/J.JCSS.2024.103532

M3 - Article

SN - 0022-0000

VL - 144

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

M1 - 103532

ER -

Preprocessing to reduce the search space: Antler structures for feedback vertex set

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this