#### Conference abstracts

Session A4 - Computational Geometry and Topology

July 12, 15:30 ~ 15:55 - Room B7

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

### Éric Colin de Verdière

### CNRS, LIGM, Université Paris-Est Marne-la-Vallée, France - eric.colindeverdiere@u-pem.fr

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 specifically designed for this problem; its running time considerably improves upon the existing bounds implicit in the literature for the more general problem of contractibility of closed curves in a $3$-manifold. The proof of the correctness of the algorithm relies on methods of $3$-manifold topology and in particular on those used in the proof of the Loop Theorem.

Joint work with Salman Parsa (Mathematical Sciences Department, Sharif University of Technology, Tehran, Iran).