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 GS is acyclic. It is one of the first few problems which were shown to be NPcomplete, and has been extensively studied from the viewpoint of approximation and parameterized algorithms. The bestknown polynomial time approximation algorithm for FVS is a 2factor 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 bestknown (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 wellknown 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:156:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772921},
ISSN = {18688969},
year = {2023},
volume = {272},
editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18590},
URN = {urn:nbn:de:0030drops185902},
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 