Time: 11am Friday, 25th May, 2012
Location: SIT 124 Boardroom
Speaker: Benjamin Burton, University of Queensland
There are many interesting and difficult algorithmic problems in
low-dimensional topology. Here we study the problem of finding a taut
structure on a 3-manifold triangulation, whose existence has implications
for both the geometry and combinatorics of the triangulation. We prove
that detecting taut structures is “hard”, in the sense that it is NP-complete.
We also prove that detecting taut structures is “not too hard”, by showing
it to be fixed-parameter tractable. This is joint work with Jonathan Spreer.