Deciding contractibility of a non-simple curve on the boundary of a 3-manifold

We present an algorithm for the following problem. Given a triangulated 3-manifold M and a (possibly non-simple) closed curve on the boundary of M, decide whether this curve is contractible in M. Our algorithm is combinatorial and runs in exponential time. This is the first algorithm that is specifi... View More