Planar kernel and grundy with d≤3, dout≤2, din≤2 are NP-complete
Planar kernel and grundy with d≤3, dout≤2, din≤2 are NP-complete
复制标题
d≤3、dout≤2、din≤2 的平面核和 grundy 是 NP 完全的
DOI：
10.1016/0166-218x(81)90003-2
复制
发表时间：
1981
期刊：
影响因子：
--
通讯作者：
A. Fraenkel
中科院分区：
文献类型：
--
作者：
A. Fraenkel
证明了即使G是度约束为dout(u)≤2、din(u)≤2和d(u)≤3的循环平面有向图，有限有向图G是否具有核K或Sprague-Grundy函数也是NP完全的。这些结果是最好的（如果 P ≠ NP），因为如果任何约束被收紧，则多项式算法要么计算 K 要么表明它们不存在。该证明对两个问题都使用平面 3 可满足性的单一归约。
It is proved that the questions whether a finite diagraphGhas a kernelKor a Sprague—Grundy functiongare NP-complete even ifGis a cyclic planar digraph with degree constraintsdout(u)≤2,din(u)≤2 andd(u)≤3. These results are best possible (if P ≠ NP) in the sense that if any of the constraints is tightened, there are polynomial algorithms which either computeKandgor show that they do not exist. The proof uses a single reduction from planar 3-satisfiability for both problems.