Parameterized complexity of discrete Morse theory

Burton, Benjamin A., Lewiner, Thomas, Paixao, Joao and Spreer, Jonathan (2016) Parameterized complexity of discrete Morse theory. ACM Transactions On Mathematical Software, 42 1: 6:1-6:24. doi:10.1145/2738034

Author Burton, Benjamin A.
Lewiner, Thomas
Paixao, Joao
Spreer, Jonathan
Title Parameterized complexity of discrete Morse theory
Journal name ACM Transactions On Mathematical Software   Check publisher's open access policy
ISSN 0098-3500
Publication date 2016-02
Year available 2016
Sub-type Article (original research)
DOI 10.1145/2738034
Open Access Status Not Open Access
Volume 42
Issue 1
Start page 6:1
End page 6:24
Total pages 24
Place of publication New York, NY United States
Publisher ACM Special Interest Group
Collection year 2017
Language eng
Abstract Optimal Morse matchings reveal essential structures of cell complexes that 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.
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status UQ
Additional Notes Although this has the same title and authors as the conference paper UQ:314216, this journal article is different - it is much longer, and contains significant additional research.

Document type: Journal Article
Sub-type: Article (original research)
Collections: School of Mathematics and Physics
HERDC Pre-Audit
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in Thomson Reuters Web of Science Article
Scopus Citation Count Cited 0 times in Scopus Article
Google Scholar Search Google Scholar
Created: Sun, 06 Mar 2016, 10:01:27 EST by Dr Benjamin Burton on behalf of Mathematics