SMS scnews item created by Zhou Zhang at Tue 12 Nov 2013 0105
Type: Seminar
Modified: Tue 12 Nov 2013 1205
Distribution: World
Expiry: 10 Dec 2013
Calendar1: 18 Nov 2013 1200-1300
CalLoc1: AGR Carslaw 829
Auth: zhangou@ (zhouz) in SMS-WASM

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

Speaker: Dr. Jonathan Spreer (Queensland)

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 

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


Seminar website: