论文标题
有向反馈顶点集的参数化算法
Parameterized Algorithms for Generalizations of Directed Feedback Vertex Set
论文作者
论文摘要
定向反馈顶点集（DFVS）问题将有向图〜$ g $作为输入，并寻求最小的顶点集〜$ s $，它以$ g $命中所有周期。这是KARP的21美元$ \ Mathsf {NP} $ - 完整问题。在Chen等人之前，解决DFV的参数化复杂性状态是一个长期的开放问题。 [STOC 2008，J。ACM2008]通过$ 4^kk展示了其固定参数的障碍！ n^{\ Mathcal {o}（1）} $ - 时间算法，其中$ k = | s | $。 在这里，我们显示了两个DFV概括的固定参数障碍性： - 找到一个最小的顶点套$ s $，以使$ g -s $的每个强组件最多都有〜$ s $：我们给出了一个算法解决此问题$ 4^k（ks+k+s）！这将Xiao [JCSS 2017]的算法概括为问题的无向版本。 - 找到最小的顶点集$ s $，以便每个非平凡的强组件的$ g-s $ is 1算出：我们给出了一个算法解决此问题的算法$ 2^{\ MATHCAL {o}（k^3）} \ cdot n^{\ cdot n^{\ nathcal {\ nathcal {o}（o} $}（1）$。 我们还通过固定参数算法解决了这些问题的相应弧版。
The Directed Feedback Vertex Set (DFVS) problem takes as input a directed graph~$G$ and seeks a smallest vertex set~$S$ that hits all cycles in $G$. This is one of Karp's 21 $\mathsf{NP}$-complete problems. Resolving the parameterized complexity status of DFVS was a long-standing open problem until Chen et al. [STOC 2008, J. ACM 2008] showed its fixed-parameter tractability via a $4^kk! n^{\mathcal{O}(1)}$-time algorithm, where $k = |S|$. Here we show fixed-parameter tractability of two generalizations of DFVS: - Find a smallest vertex set $S$ such that every strong component of $G - S$ has size at most~$s$: we give an algorithm solving this problem in time $4^k(ks+k+s)!\cdot n^{\mathcal{O}(1)}$. This generalizes an algorithm by Xiao [JCSS 2017] for the undirected version of the problem. - Find a smallest vertex set $S$ such that every non-trivial strong component of $G - S$ is 1-out-regular: we give an algorithm solving this problem in time $2^{\mathcal{O}(k^3)}\cdot n^{\mathcal{O}(1)}$. We also solve the corresponding arc versions of these problems by fixed-parameter algorithms.
