Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Legrand-Duchesne, Clément; Rai, Ashutosh; Tancer, Martin https://www.dagstuhl.de/lipics License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-164296
URL:

; ;

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


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