Presented by: 
Ben Burton (UQ)
Date: 
Tue 21 May, 3:00 pm - 4:00 pm
Venue: 
Room 442, Building 67

In algorithmic graph theory, Courcelle’s "metatheorem" essentially gives us theorems for free: it shows that, if an algorithmic problem can be framed in monadic second-order logic, then it can be solved in linear time for graphs of bounded treewidth.  We prove such a metatheorem for triangulations of manifolds.  We use this metatheorem to recover some recent complexity results on topological algorithms, and to prove a new result on the fixed-parameter tractability of computing powerful invariants on 3-manifolds.

This is joint work with Rod Downey.