License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2023.56
URN: urn:nbn:de:0030-drops-185902
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18590/
Jana, Satyabrata ;
Lokshtanov, Daniel ;
Mandal, Soumen ;
Rai, Ashutosh ;
Saurabh, Saket
Parameterized Approximation Scheme for Feedback Vertex Set
Abstract
Feedback Vertex Set (FVS) is one of the most studied vertex deletion problems in the field of graph algorithms. In the decision version of the problem, given a graph G and an integer k, the question is whether there exists a set S of at most k vertices in G such that G-S is acyclic. It is one of the first few problems which were shown to be NP-complete, and has been extensively studied from the viewpoint of approximation and parameterized algorithms. The best-known polynomial time approximation algorithm for FVS is a 2-factor approximation, while the best known deterministic and randomized FPT algorithms run in time ?^*(3.460^k) and ?^*(2.7^k) respectively.
In this paper, we contribute to the newly established area of parameterized approximation, by studying FVS in this paradigm. In particular, we combine the approaches of parameterized and approximation algorithms for the study of FVS, and achieve an approximation guarantee with a factor better than 2 in randomized FPT running time, that improves over the best known parameterized algorithm for FVS. We give three simple randomized (1+ε) approximation algorithms for FVS, running in times ?^*(2^{εk}⋅ 2.7^{(1-ε)k}), ?^*(({(4/(1+ε))^{(1+ε)}}⋅{(ε/3)^ε})^k), and ?^*(4^{(1-ε)k}) respectively for every ε ∈ (0,1). Combining these three algorithms, we obtain a factor (1+ε) approximation algorithm for FVS, which has better running time than the best-known (randomized) FPT algorithm for every ε ∈ (0, 1). This is the first attempt to look at a parameterized approximation of FVS to the best of our knowledge. Our algorithms are very simple, and they rely on some well-known reduction rules used for arriving at FPT algorithms for FVS.
BibTeX - Entry
@InProceedings{jana_et_al:LIPIcs.MFCS.2023.56,
author = {Jana, Satyabrata and Lokshtanov, Daniel and Mandal, Soumen and Rai, Ashutosh and Saurabh, Saket},
title = {{Parameterized Approximation Scheme for Feedback Vertex Set}},
booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
pages = {56:1--56:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-292-1},
ISSN = {1868-8969},
year = {2023},
volume = {272},
editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18590},
URN = {urn:nbn:de:0030-drops-185902},
doi = {10.4230/LIPIcs.MFCS.2023.56},
annote = {Keywords: Feedback Vertex Set, Parameterized Approximation}
}
|
Keywords: |
|
Feedback Vertex Set, Parameterized Approximation |
|
Collection: |
|
48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
21.08.2023 |
