
arXiv: 2111.05001
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.
unknot recognition, Computational Geometry (cs.CG), FOS: Computer and information sciences, Geometric Topology (math.GT), Computational Complexity (cs.CC), Reidemeister moves, 004, Computer Science - Computational Complexity, Mathematics - Geometric Topology, W[P]-complete, FOS: Mathematics, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Knots and links in the \(3\)-sphere, Computer Science - Computational Geometry, parameterized complexity, ddc: ddc:004
unknot recognition, Computational Geometry (cs.CG), FOS: Computer and information sciences, Geometric Topology (math.GT), Computational Complexity (cs.CC), Reidemeister moves, 004, Computer Science - Computational Complexity, Mathematics - Geometric Topology, W[P]-complete, FOS: Mathematics, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Knots and links in the \(3\)-sphere, Computer Science - Computational Geometry, parameterized complexity, ddc: ddc:004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
