2:00 pm, Seminar Hall
Exploring parameterised complexity in computational topology
Benjamin Burton
Computational Geometry & Topology Group, University of Queensland, Australia.
18-11-14

---

Abstract

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 some initial forays into the parameterised complexity of topological problems, including both fixed-parameter-tractability and W[P]-hardness results. Includes joint work with Rod Downey, Thomas Lewiner, João Paixão, William Pettersson, and Jonathan Spreer.