论文标题
击中长时间的循环是固定参数
Hitting Long Directed Cycles is Fixed-Parameter Tractable
论文作者
论文摘要
在定向的长周期命中集中}问题我们得到了一个定向的图形$ g $，其任务是在最多$ k $ dertices/arcs找到一个$ s $的集合，以便$ g-s $没有长度长于$ \ ell $的循环。我们表明，问题可以在时间$ 2^{\ Mathcal O（\ ell k^3 \ log k + k + k^5 \ log k \ log k \ log \ ell）} \ cdot n^{\ mathcal o（1）} $，也就是说，它是固定的 - 参数tractable tractable tractable（fpt）参数。该算法可以看作是{\ sc混合图形反馈顶点}的固定参数易处理性的深度概括} [Bonsma和Lokshtanov Wads 2011]，这已经是（无方向的）{\ sc反馈vertex and sc crousty} and sc crounds {creste}的固定参数的普遍概括，\ sc sc sc sc acc crounds} and sc acc crouts} and crests {\ sc。在参数化算法中。该算法需要对图形结构进行重大见解，而无需定向循环长度长于$ \ ell $，并且可以被视为近似算法的精确版本，从ERD {ő} s-p {ó} s-p {ó} sa属性中的eRD {ő} s-p {ó} sa属性指示，该属性由Kreutzer和kreutzer and Kawarabayashi [STOCCOC 2015]进行了指示。
In the Directed Long Cycle Hitting Set} problem we are given a directed graph $G$, and the task is to find a set $S$ of at most $k$ vertices/arcs such that $G-S$ has no cycle of length longer than $\ell$. We show that the problem can be solved in time $2^{\mathcal O(\ell k^3\log k + k^5\log k\log\ell)}\cdot n^{\mathcal O(1)}$, that is, it is fixed-parameter tractable (FPT) parameterized by $k$ and $\ell$. This algorithm can be seen as a far-reaching generalization of the fixed-parameter tractability of {\sc Mixed Graph Feedback Vertex Set} [Bonsma and Lokshtanov WADS 2011], which is already a common generalization of the fixed-parameter tractability of (undirected) {\sc Feedback Vertex Set} and the {\sc Directed Feedback Vertex Set} problems, two classic results in parameterized algorithms. The algorithm requires significant insights into the structure of graphs without directed cycles length longer than $\ell$ and can be seen as an exact version of the approximation algorithm following from the Erd{ő}s-P{ó}sa property for long cycles in directed graphs proved by Kreutzer and Kawarabayashi [STOC 2015].
