论文标题
改进的FPT算法删除到类似森林的结构
Improved FPT Algorithms for Deletion to Forest-like Structures
论文作者
论文摘要
反馈顶点集问题无疑是参数化复杂性最有研究的问题之一。在此问题中，给定无向图$ g $和非负整数$ k $，目的是测试最多$ k $的子集$ s \ subseteq v（g）$的子集$ s \ subseteq v（g）$，以便$ g-s $是森林。经过一长串的改进，最近，Li和Nederlof [Soda，2020]设计了一种随机算法，用于在时间上运行的问题$ \ Mathcal {o}^{\ star}（\ star}（2.7^k）$。在参数化的复杂性文献中，已经研究了反馈顶点集周围的几个问题。其中一些包括独立的反馈顶点集（其中集合$ s $是$ g $中的独立集），几乎是森林删除和伪造的删除。在伪造删除中，$ g-s $中的每个连接组件最多都有一个周期。但是，在几乎森林删除中，输入是图$ g $和\ mathbb {n} $中的非负整数$ k，\ ell \ in \ in \ mathbb {n} $，目的是测试最多是否存在$ g-s $的$ g-s $是$ g-s $的$ g-s $ ake $ g el $ f eeld $ et forest forest的顶点$ s $ s $。在本文中，使用LI和NEDERLOF的方法[SODA，2020年]，我们获得了所有这些问题的当前最快算法。特别是我们获得了以下随机算法。 1）独立反馈顶点集可以在时间上求解$ \ Mathcal {o}^{\ star}（2.7^k）$。 2）可以在时间$ \ Mathcal {o}^{\ star}（2.85^k）$的时间内解决伪森林删除。 3）几乎可以用$ \ Mathcal {o}^{\ star}（\ min \ {2.85^k \ cdot 8.54^\ ell，2.7^k \ cdot 36.61^\ ell，3^k \ cdot 1.78^\ ell \ ell \ ell \ ell \ ell \ ell \ ell \ ell \ ell \ ell \ ell \ ell \ ell \ ell \ ell \ ell \ ell \ ell \ ell \ ell \ ell \ ell \ ell \ ell \ ell \ ell \ ell \ ell \ ell \ e}）$。
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 algorithms for all these problems. In particular we obtain following randomized algorithms. 1) Independent Feedback Vertex Set can be solved in time $\mathcal{O}^{\star}(2.7^k)$. 2) Pseudo Forest Deletion can be solved in time $\mathcal{O}^{\star}(2.85^k)$. 3) Almost Forest Deletion can be solved in $\mathcal{O}^{\star}(\min\{2.85^k \cdot 8.54^\ell,2.7^k \cdot 36.61^\ell,3^k \cdot 1.78^\ell\})$.
