Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.88
URN: urn:nbn:de:0030-drops-164296
URL: https://drops.dagstuhl.de/opus/volltexte/2022/16429/
Legrand-Duchesne, Clément ; Rai, Ashutosh ; Tancer, Martin
Parameterized Complexity of Untangling Knots
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{legrandduchesne_et_al:LIPIcs.ICALP.2022.88,
author = {Legrand-Duchesne, Cl\'{e}ment and Rai, Ashutosh and Tancer, Martin},
title = {{Parameterized Complexity of Untangling Knots}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {88:1--88:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-235-8},
ISSN = {1868-8969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16429},
URN = {urn:nbn:de:0030-drops-164296},
doi = {10.4230/LIPIcs.ICALP.2022.88},
annote = {Keywords: unknot recognition, parameterized complexity, Reidemeister moves, W\lbrackP\rbrack-complete}
}
| Keywords: | unknot recognition, parameterized complexity, Reidemeister moves, W[P]-complete | |
| Seminar: | 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 28.06.2022 |
