Type: Seminar

Modified: Tue 12 Nov 2013 1205

Distribution: World

Expiry: 10 Dec 2013

Auth: zhangou@60.225.178.103 (zhouz) in SMS-WASM

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/