SMOR Seminar: Untangling knots using combinatorial optimisation
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.