论文标题
在时间中解决R-PESEFOREST删除问题，而与R无关
Solving the r-pseudoforest Deletion Problem in Time Independent of r
论文作者
论文摘要
反馈顶点集问题是研究最多的参数化问题之一。已经研究了该问题的几个概括，其中一个是要删除顶点以获取接近无环的图形。在本文中，我们为删除$ k $顶点删除的问题提供了FPT算法，以获取$ r $ $ -PSEUDOFOREST。如果我们可以从每个组件中删除最多的$ r $边缘以获取森林，则图形是$ r $ -pseudoforest。 Philip等。引入了此问题，并给出了$ o^*（c_ {r}^{k}）$算法，其中$ c_r $依赖于$ r $ double指数。相比之下，我们的算法在时间上运行$ o^*（（（10k）^{k}）$，独立于$ r $。
The feedback vertex set problem is one of the most studied parameterized problems. Several generalizations of the problem have been studied where one is to delete vertices to obtain graphs close to acyclic. In this paper, we give an FPT algorithm for the problem of deleting at most $k$ vertices to get an $r$-pseudoforest. A graph is an $r$-pseudoforest if we can delete at most $r$ edges from each component to get a forest. Philip et al. introduced this problem and gave an $O^*(c_{r}^{k})$ algorithm for it, where $c_r$ depends on $r$ double exponentially. In comparison, our algorithm runs in time $O^*((10k)^{k})$, independent of $r$.
