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 - bab@maths.uq.edu.au
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).