Can I read Improved FPT Algorithms for Deletion to Forest-like Structures on EtoBox?

Improved FPT Algorithms for Deletion to Forest-like Structures by Gowda, Kishen N.; Lonkar, Aditya; Panolan, Fahad; Patel, Vraj; Saurabh, Saket is a scholarly article available to read on EtoBox.

What is Improved FPT Algorithms for Deletion to Forest-like Structures about?

The Feedback Vertex Set problem is undoubtedly one of the most well-studied problems in Parameterized Complexity. In this problem, given an undirected graph $G$ and a non-negative integer $k$, the objective is to test whether there exists a subset $S\subseteq V(G)$ of size at most $k$ such that $G-S$ 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 $\mathcal{O}^{\star}(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 $G-S$ has at most one cycle in it. However, in Almost Forest Deletion, the input is a graph $G$ and non-negative integers $k,\ell \in \mathbb{N}$, and the objective is to test whether there exists a vertex subset $S$ of size at most $k$, such that $G-S$ is $\ell$ edges away from a forest. In this paper, using the methodology of Li and Nederlof [SODA, 2020], we obtain the current fastest algori

Author

Gowda, Kishen N.; Lonkar, Aditya; Panolan, Fahad; Patel, Vraj; Saurabh, Saket

Published

2020

Language

EN