Parameterized Complexity of Discrete Morse Theory
Jonathan Spreer
Queensland
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.