Deciding whether a diagram of a knot can be untangled with a given number of moves (as a part of the input) is known to be NP-complete. In this paper we determine the parameterized complexity of this problem with respect to a natural parameter called defect. Roughly speaking, it measures the efficiency of the moves used in the shortest untangling sequence of Reidemeister moves. We show that the II- moves in a shortest untangling sequence can be essentially performed greedily. Using that, we show that this problem belongs to W[P] when parameterized by the defect. We also show that this problem is W[P]-hard by a reduction from Minimum axiom set.
翻译:确定结图能否与一定数量的移动( 作为输入的一部分) 脱钩( ) 已知为 NP 完成 。 在本文中, 我们确定这个问题对于称为缺陷的自然参数的参数复杂性 。 粗略地说, 它测量 Reidemeister 移动中最短的未切换序列中使用的移动效率 。 我们显示, 以最短的不切换序列的 II 移动基本上可以贪婪地进行 。 使用它, 我们显示这个问题在标注缺陷时属于 W [P] 。 我们还显示, 这个问题在最小值设置的减值中是 W [P] 硬的 。