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

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.