3
$\begingroup$

Given a number of knots, I would like to know if they are linked. I know that the linking number can tell if two knots are linked.

There is any method that completely solves this problem?

$\endgroup$
1
  • $\begingroup$ In knot theory, people would use the terminology "is there an algorithm to decide if a link is split?" The answer is yes. Neil Hoffman's answer is one practical way to attack the problem. In practice there are many quite fast ways to solve the problem. $\endgroup$ Jun 23, 2014 at 2:40

2 Answers 2

11
$\begingroup$

The linking number does not tell if two knots are linked, see for example the Whitehead link: http://en.wikipedia.org/wiki/Whitehead_link

I think that the best algorithms for the unlink problem follow closely the ones for the unknot, none of these being polynomial. The starting reference for these is Hass, Lagarias and Pippenger, who proved that the problem is in NP, and their algorithm relies on normal surface theory.

Marc Lackenby proved last year that one can split the unlink using only a polynomial number of Reidemeister moves. Therefore, an alternative algorithm is to brute force all the possible Reidemeister moves up to this polynomial bound ($48c^{11}$ if $c$ is the number of crossings) .

$\endgroup$
3
  • 1
    $\begingroup$ I don't understand: doesn't this give $48c^{11}$ in the EXPONENT of the running time? $\endgroup$
    – Igor Rivin
    Jun 17, 2014 at 15:25
  • 1
    $\begingroup$ @IgorRivin Yes, from Lackenby's paper "It is worth pointing out that this does not actually improve our knowledge of the complexity class of the unknot recognition problem." $\endgroup$ Jun 17, 2014 at 16:14
  • $\begingroup$ @EdgarA.BeringIV Thanks! It sounds like this does not help on a practical level, either. $\endgroup$
    – Igor Rivin
    Jun 17, 2014 at 16:55
2
$\begingroup$

For this method, I am using the fact that a link is split if and only if the double branched cover of the link has a non-separating two sphere that does not bound a ball. Here is an algorithm that I believe is as "practical as it can be" using existing tools.

The first step is to check the homology of the double branched cover. If $G = <m_1,m_2, ... m_n |r_1,..,r_k>$ is a Wirtinger presentation for the link group, then the kernel of $f:G \rightarrow G/\langle \langle m_i^2 \rangle \rangle$ must have infinite abelianization for the link to be split. Strictly, speaking this step is unnecessary, but the next step is in going to be fairly slow, making it worth a mention.

The next step would be to check that the double branched cover of your link is reducible or irreducible. The software Regina can solve this problem. Because it enumerates and checks all normal surfaces, Regina will be slow for large links. If the double branched cover is reducible, Regina can cut along the normal and incompressible $S^2$. Checking the number of connected components determines if the sphere was separating. This can be done just using out of the box Regina. However, if you need to check a large set of complicated enough examples, you may be able to tweak the source code of the ${\tt T.isIrreducible()}$ function in order to tailor yourself a slightly better algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.