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$.
翻译：反馈顶点设置问题是最研究最多的参数化问题之一。 已经研究了一些问题的一般化, 即删除脊椎以获取接近环形的图表。 在本文中, 我们给出了一种FPT算法, 解决以最多k$为单位删除脊椎以获得一个$- suedoforest的问题。 一张图是一个$- sudoforest, 如果我们能从每个部件中以最多$为单位删除边缘以获取森林。 Philip 等人介绍了这个问题, 并给出了一个$( c ⁇ r ⁇ k}) $( $_ r$) 的算法, 其中$_ r$( $) 的算法以倍速计算。 相比之下, 我们的算法运行时间为 $( 10k) $( 10k) ($) 。
相关内容
微信扫码咨询专知VIP会员