GTA Seminar : Spreer -- Parameterized Complexity of Discrete Morse Theory

Speaker: Dr. Jonathan Spreer (Queensland)

http://www.smp.uq.edu.au/node/106/1142

Time: **Monday**, Nov. 18, 12NOON--1PM

Room: AGR (Carslaw 829)

Lunch: after the talk, at Law Annex Cafe. 

---------------------------------------------- 

Title: Parameterized Complexity of Discrete Morse Theory   

Abstract: Optimal Morse matchings reveal essential structures 
of cell complexes which lead to powerful tools to study discrete 
3-manifolds. However, such matchings are known to be NP-hard to 
compute on 3-manifolds. Here, we refine the study of the complexity 
of problems related to discrete Morse theory in terms of parameterized 
complexity. On the one hand we prove that the erasability problem 
is W[P]-complete on the natural parameter. On the other hand we 
propose an algorithm for computing optimal Morse matchings on 
triangulations of 3-manifolds which is fixed-parameter tractable 
in the treewidth of the dual graph of the triangulation as well 
as the bipartite graph representing the adjacency of the 1- and 
2-simplexes.

This is joint work with Ben Burton, Thomas Lewiner and Joao Paixao.

----------------------------------------------

Seminar website:

http://www.maths.usyd.edu.au/u/SemConf/Geometry/