Abstract
The Feedback Vertex Set problem is undoubtedly one of the most wellstudied problems in Parameterized Complexity. In this problem, given an undirected graph G and a nonnegative integer k, the objective is to test whether there exists a subset S ⊆ V(G) of size at most k such that GS is a forest. After a long line of improvement, recently, Li and Nederlof [SODA, 2020] designed a randomized algorithm for the problem running in time 𝒪^⋆(2.7^k). In the Parameterized Complexity literature, several problems around Feedback Vertex Set have been studied. Some of these include Independent Feedback Vertex Set (where the set S should be an independent set in G), Almost Forest Deletion and Pseudoforest Deletion. In Pseudoforest Deletion, each connected component in GS has at most one cycle in it. However, in Almost Forest Deletion, the input is a graph G and nonnegative integers k,𝓁 ∈ ℕ, and the objective is to test whether there exists a vertex subset S of size at most k, such that GS is 𝓁 edges away from a forest. In this paper, using the methodology of Li and Nederlof [SODA, 2020], we obtain the current fastest algorithms for all these problems. In particular we obtain following randomized algorithms.
1) Independent Feedback Vertex Set can be solved in time 𝒪^⋆(2.7^k).
2) Pseudo Forest Deletion can be solved in time 𝒪^⋆(2.85^k).
3) Almost Forest Deletion can be solved in 𝒪^⋆(min{2.85^k ⋅ 8.54^𝓁, 2.7^k ⋅ 36.61^𝓁, 3^k ⋅ 1.78^𝓁}).
BibTeX  Entry
@InProceedings{gowda_et_al:LIPIcs:2020:13378,
author = {Kishen N. Gowda and Aditya Lonkar and Fahad Panolan and Vraj Patel and Saket Saurabh},
title = {{Improved FPT Algorithms for Deletion to ForestLike Structures}},
booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)},
pages = {34:134:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771733},
ISSN = {18688969},
year = {2020},
volume = {181},
editor = {Yixin Cao and SiuWing Cheng and Minming Li},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13378},
URN = {urn:nbn:de:0030drops133781},
doi = {10.4230/LIPIcs.ISAAC.2020.34},
annote = {Keywords: Parameterized Complexity, Independent Feedback Vertex Set, PseudoForest, Almost Forest, Cut and Count, Treewidth}
}
Keywords: 

Parameterized Complexity, Independent Feedback Vertex Set, PseudoForest, Almost Forest, Cut and Count, Treewidth 
Collection: 

31st International Symposium on Algorithms and Computation (ISAAC 2020) 
Issue Date: 

2020 
Date of publication: 

04.12.2020 