License: Creative Commons Attribution 4.0 International 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16429/
Go to the corresponding LIPIcs Volume Portal

Legrand-Duchesne, Clément ; Rai, Ashutosh ; Tancer, Martin

Parameterized Complexity of Untangling Knots

pdf-format:
LIPIcs-ICALP-2022-88.pdf (1.0 MB)

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
Collection: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Issue Date: 2022
Date of publication: 28.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI