2026-08-17T17:35:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16429 2024-03-06T10:57:27Z ddc:004 open_access

Parameterized Complexity of Untangling Knots Legrand-Duchesne, Clément Rai, Ashutosh Tancer, Martin unknot recognition parameterized complexity Reidemeister moves W[P]-complete 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Clément Legrand-Duchesne and Ashutosh Rai and Martin Tancer 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.88 urn:nbn:de:0030-drops-164296 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.88 eng https://creativecommons.org/licenses/by/4.0/legalcode