FoCM 2014 conference

Workshop B2 - Computational Topology and Geometry

December 17, 17:30 ~ 17:55 - Room A22

Parameterised complexity in 3-manifold topology

Benjamin Burton

The University of Queensland, Australia   -

Decision problems on 3-manifolds are notoriously difficult: the mere existence of an algorithm is often a major result, even ``simple'' problems have best-known algorithms that are exponential time, and many important algorithms have yet to be studied from a complexity viewpoint. In practice, however, some of these algorithms run surprisingly well in experimental settings. In this talk we discuss why parameterised complexity now looks to be the ``right'' tool to explain this behaviour. We present encouraging initial results on the parameterised complexity of topological problems, including both fixed-parameter-tractability and W[P]-hardness results, and discuss current directions of ongoing research.

Joint work with Rodney Downey (Victoria University of Wellington, New Zealand), Thomas Lewiner (PUC University of Rio de Janeiro, Brazil), João Paixão (PUC University of Rio de Janeiro, Brazil), William Pettersson (The University of Queensland, Australia) and Jonathan Spreer (The University of Queensland, Australia).

View abstract PDF