Document Open Access Logo

Parameterized Complexity of Untangling Knots

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

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.88.pdf
  • Filesize: 0.99 MB
  • 17 pages

Document Identifiers

Author Details

Clément Legrand-Duchesne
  • Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, F-33400 Talence, France
Ashutosh Rai
  • Department of Mathematics, IIT Delhi, Hauz Khas, New Delhi, India
Martin Tancer
  • Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic

Funding

  • Legrand-Duchesne, Clément: Part of this work has been done when C. L.-D. visited Charles University, whose stay was partially supported by the GAČR grant 19-04113Y.
  • Rai, Ashutosh: Supported by SERB grant SRG/2021/002412.
  • Tancer, Martin: Supported by the GAČR grant 19-04113Y.

Cite AsGet BibTex

Clément Legrand-Duchesne, Ashutosh Rai, and Martin Tancer. Parameterized Complexity of Untangling Knots. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 88:1-88:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.88

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Geometric topology
  • Theory of computation → Problems, reductions and completeness
Keywords
  • unknot recognition
  • parameterized complexity
  • Reidemeister moves
  • W[P]-complete

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. N. Alon, G. Z. Gutin, E. J. Kim, S. Szeider, and A. Yeo. Solving MAX-r-sat above a tight lower bound. Algorithmica, 61(3):638-655, 2011. Google Scholar
  2. U. Bauer, A. Rathod, and J. Spreer. Parametrized Complexity of Expansion Height. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms (ESA 2019), volume 144 of Leibniz International Proceedings in Informatics (LIPIcs), pages 13:1-13:15, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  3. B. A. Burton, T. Lewiner, J. Paixão, and J. Spreer. Parameterized complexity of discrete Morse theory. ACM Trans. Math. Software, 42(1):Art. 6, 24, 2016. Google Scholar
  4. R. Crowston, M. R. Fellows, G. Z. Gutin, M. Jones, E. J. Kim, F. Rosamond, I. Z. Ruzsa, S. Thomassé, and A. Yeo. Satisfying more than half of a system of linear equations over GF(2): A multivariate approach. J. Comput. Syst. Sci., 80(4):687-696, 2014. Google Scholar
  5. R. Crowston, M. Jones, G. Muciaccia, G. Philip, A. Rai, and S. Saurabh. Polynomial kernels for lambda-extendible properties parameterized above the Poljak-Turzik bound. In A. Seth and N. K. Vishnoi, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2013, December 12-14, 2013, Guwahati, India, volume 24 of LIPIcs, pages 43-54. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013. Google Scholar
  6. M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, Ma. Pilipczuk, Mi. Pilipczuk, and S. Saurabh. Parameterized algorithms. Springer, Cham, 2015. Google Scholar
  7. R. G. Downey and M. R. Fellows. Fundamentals of Parameterized Complexity. Springer, 2013. Google Scholar
  8. J. Flum and M. Grohe. Parameterized complexity theory. Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin, 2006. Google Scholar
  9. G. Z. Gutin, L. van Iersel, M. Mnich, and A. Yeo. Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables. J. Comput. Syst. Sci., 78(1):151-163, 2012. Google Scholar
  10. G. Z. Gutin, E. J. Kim, M. Lampis, and V. Mitsou. Vertex cover problem parameterized above and below tight bounds. Theory Comput. Syst., 48(2):402-410, 2011. Google Scholar
  11. G. Z. Gutin and V. Patel. Parameterized traveling salesman problem: Beating the average. SIAM J. Discret. Math., 30(1):220-238, 2016. Google Scholar
  12. W. Haken. Theorie der Normalflächen. Acta Math., 105:245-375, 1961. Google Scholar
  13. J. Hass, J. C. Lagarias, and N. Pippenger. The computational complexity of knot and link problems. J. ACM, 46(2):185-211, 1999. Google Scholar
  14. L. H. Kauffman and S. Lambropoulou. Hard unknots and collapsing tangles. In Introductory lectures on knot theory, volume 46 of Ser. Knots Everything, pages 187-247. World Sci. Publ., Hackensack, NJ, 2012. Google Scholar
  15. D. Koenig and A. Tsvietkova. NP-hard problems naturally arising in knot theory. Trans. Amer. Math. Soc. Ser. B, 8:420-441, 2021. Google Scholar
  16. G. Kuperberg. Knottedness is in NP, modulo GRH. Adv. Math., 256:493-506, 2014. Google Scholar
  17. M. Lackenby. A polynomial upper bound on Reidemeister moves. Ann. of Math. (2), 182(2):491-564, 2015. Google Scholar
  18. M. Lackenby. Elementary knot theory. In Lectures on geometry, Clay Lect. Notes, pages 29-64. Oxford Univ. Press, Oxford, 2017. Google Scholar
  19. M. Lackenby. The efficient certification of knottedness and Thurston norm. Adv. Math., 387, 2021. Google Scholar
  20. M. Lackenby. Marc Lackenby announces a new unknot recognition algorithm that runs in quasi-polynomial time, 2021. URL: https://www.maths.ox.ac.uk/node/38304.
  21. M. Mahajan and V. Raman. Parameterizing above guaranteed values: MaxSat and MaxCut. J. Algorithms, 31(2):335-354, 1999. Google Scholar
  22. M. Mahajan, V. Raman, and S. Sikdar. Parameterizing above or below guaranteed values. J. Comput. Syst. Sci., 75(2):137-153, 2009. Google Scholar
  23. A. de Mesmay, Y. Rieck, E. Sedgwick, and M. Tancer. The unbearable hardness of unknotting. Adv. Math., 381:107648, 36, 2021. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact