Lune

SODA2021Top-tier venue

Unlinking, splitting, and some other NP-hard problems in knot theory

Dale Koenig, Anastasiia Tsvietkova

Abstract

We prove that certain problems naturally arising in knot theory are NP-hard or NP-complete. These are the problems of determining whether a link has an unlinking or splitting number k, finding a k-component unlink as a sublink, and finding a k-component alternating sublink.

The unlinking number of a link is the minimum number of crossing changes required for it to become an unlink, minimized over all diagrams of the link. Similarly, splitting number is the number of changes for the link to become split. Problems concerning unlinking and splitting numbers have a long history in topology and knot theory. At the same time, nothing is known about computability or complexity of these problems. A recent breakthrough by Lackenby suggests an algorithm to determine whether a hyperbolic link satisfying certain restrictions has unlinking or splitting number one [11], but no algorithm for the general case is yet known. We therefore provide the first bounds on the complexity of the general unlinking and splitting number problems. Our proof of NP-hardness for unlinking and splitting numbers is built upon our other proof, that of NP-hardness of unlink as a sublink problem. This problem is a special case (i.e. a restriction) of the sublink problem, previously proven to be NP-hard [10]. More generally, for any property X of links one can also consider decision problems of the form "Given a diagram of a link L and a positive integer k, is there a k component sublink of L with the property X?" We show that this is also NP-hard if X is the property of being an alternating link.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. Directed Tangle Tree-Decompositions and ApplicationsArchontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung KwonSODA 2022 · 5 citations
  2. Untangling Graphs on SurfacesÉric Colin de Verdière, Vincent Despré, Loïc DuboisSODA 2024
  3. Shellability Is Hard Even for BallsPavel Paták, Martin TancerSTOC 2023 · 1 citation
  4. Forbidden Subgraphs of Graphs with Low BandwidthMaria Chudnovsky, Daniel Lokshtanov, Eran NevoSTOC 2026
  5. Braiding VineyardsErin W. Chambers, Christopher Fillmore, Elizabeth Stephenson, Mathijs WintraeckenSODA 2026
Dusk over the sea between two cliffs drawn in fine vertical lines