论文标题
关于2分期的参数化复杂性
On the parameterized complexity of 2-partitions
论文作者
论文摘要
我们给出了一个FPT算法，用于确定是否可以将顶点$ d $划分为两个不相交集合$ v_1，v_2 $，从而使$ v_1 $引起的digraph $ d [v_1] $具有有指导性的digraph $ d [v_1 $ d [v_1 $ dev_2] $ v_1 $的顶点。 $ | v_i | \ geq k_i $，其中$ k_1，k_2 $是输入的一部分。这解决了[1,4]的开放问题。
We give an FPT algorithm for deciding whether the vertex set a digraph $D$ can be partitioned into two disjoint sets $V_1,V_2$ such that the digraph $D[V_1]$ induced by $V_1$ has a vertex that can reach all other vertices by directed paths, the digraph $D[V_2]$ has no vertex of in-degree zero and $|V_i|\geq k_i$, where $k_1,k_2$ are part of the input. This settles an open problem from[1,4].
