@Article{Burton:2015:PCD,
  author =       "Benjamin A. Burton and Thomas Lewiner  and 
                  Jo\~ao Paix\~ao and Jonathan Spreer",
  title =        "Parameterized Complexity of Discrete {Morse} Theory",
  journal =      "{ACM} Transactions on Mathematical Software",
  accepted =     "18 February 2015",
  upcoming =     "true", 
  abstract =     "
                  Optimal Morse matchings reveal essential structures of
                  cell complexes which lead to powerful tools to study
                  discrete geometrical objects, in particular discrete
                  3-manifolds. However, such matchings are known to be
                  NP-hard to compute on 3-manifolds, through a reduction to
                  the erasability problem. 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 bipartite graph
                  representing the adjacency of the 1- and 2-simplices. This
                  algorithm also shows fixed parameter tractability for
                  problems such as erasability and maximum alternating
                  cycle-free matching. We further show that these results
                  are also true when the treewidth of the dual graph of the
                  triangulated 3-manifold is bounded. Finally, we discuss
                  the topological significance of the chosen parameters and
                  investigate the respective treewidths of simplicial and
                  generalized triangulations of 3-manifolds.",
}