Parameterized Algorithms for Generalizations of Directed Feedback Vertex Set
Parameterized Algorithms for Generalizations of Directed Feedback Vertex Set
复制标题
DOI：
10.1007/978-3-030-17402-6_21
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Alexander Göke;D. Marx;Matthias Mnich
中科院分区：
文献类型：
--
作者：
Alexander Göke;D. Marx;Matthias Mnich
DirectedFeedback顶点集(DFVS)问题以有向图G为输入，寻找满足所有循环的最小顶点集S。这是卡普21个完整问题之一。在Chen等人之前，解决DFVS的参数化复杂状态一直是一个悬而未决的问题。在这里，我们证明了DFVS的两个推广的固定参数可处理性：找到一个最小顶点集，使得每个强分支都至少有大小：我们给出了一个及时解决这个问题的算法；找到一个最小顶点集，使得每个非平凡强分支都是1-非正则的：我们给出了一个及时解决这个问题的算法，我们也用固定参数算法解决了这些问题的相应圆弧版本。
The DirectedFeedbackVertexSet(DFVS) problem takes as input a directed graphGand seeks a smallest vertex setSthat hits all cycles inG. This is one of Karp’s 21-complete problems. Resolving the parameterized complexity status of DFVS was a long-standing open problem until Chen et al. in 2008 showed its fixed-parameter tractability via a-time algorithm, where.Here we show fixed-parameter tractability of two generalizations of DFVS:Find a smallest vertex setSsuch that every strong component ofhas size at mosts: we give an algorithm solving this problem in time.Find a smallest vertex setSsuch that every non-trivial strong component ofis 1-out-regular: we give an algorithm solving this problem in time.We also solve the corresponding arc versions of these problems by fixed-parameter algorithms.