Untangling knots using combinatorial optimisation
Ben Burton
(Queensland)
Abstract
Unknot recognition is the algorithmic problem of determining whether a knot (i.e., a closed loop) in 3-dimensional space can be untangled. It is a major unsolved problem as to whether this problem has a fast polynomial time solution. Here we present the first conclusive algorithm for unknot recognition which, although exponential time in theory, exhibits a clear polynomial time behaviour in exhaustive practical experiments. The algorithm makes significant use of techniques from combinatorial optimisation, and uses a branch-and-bound framework with linear programming steps. We also introduce the topological software package Regina (in which the algorithm was implemented), and discuss the relevance of our results to other difficult problems in computational topology. This is joint work with Melih Ozlen.