Parameterized Complexity of Discrete Morse Theory

DOI10.1145/2738034zbMath1347.68165arXiv1303.7037OpenAlexW2288437196WikidataQ113310253 ScholiaQ113310253MaRDI QIDQ2828168

João Paixão, Thomas Lewiner, Jonathan Spreer, Benjamin A. Burton

Publication date: 24 October 2016

Published in: ACM Transactions on Mathematical Software, Proceedings of the twenty-ninth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1303.7037

zbMATH Keywords

treewidthcollapsibilityfixed parameter tractabilityfixed-parameter tractabilityparameterized complexitycomputational topologydiscrete Morse theoryerasabilityalternating cycle-free matchingW[P-completeness]W[\(P\)-completeness]

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Triangulating manifolds (57Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Approximation algorithms for Max Morse matching, Courcelle's theorem for triangulations, On the pathwidth of hyperbolic 3-manifolds, An entropy-based persistence barcode, Discrete Morse theory for the moduli spaces of polygonal linkages, or solitaire on a circle, Collapsibility to a subcomplex of a given dimension is NP-complete, Unnamed Item, Unnamed Item, Unnamed Item, Frontiers of sphere recognition in practice

Uses Software

• Regina
• simpcomp
• Library of Triangulations
• Simplicial complex library
• GitHub
• LibTW

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Treewidth. Computations and approximations
• Morse theory for cell complexes
• Optimal discrete Morse functions for 2-manifolds
• A new decomposition theorem for 3-manifolds
• Incremental construction properties in dimension two -- shellability, extendable shellability and vertex decomposability
• 0-efficient triangulations of 3-manifolds
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
• A computationally intractable problem on simplicial complexes
• On discrete Morse functions and combinatorial decompositions
• Simplicial complexes of graphs
• Seifert manifolds
• On the dunce hat
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Affine structures in 3-manifolds. V: The triangulation theorem and Hauptvermutung
• Perfect Discrete Morse Functions on Triangulated 3-Manifolds
• Computational Discrete Morse Theory for Divergence-Free 2D Vector Fields
• Minimum volume cusped hyperbolic three-manifolds
• Computing Optimal Discrete Morse Functions
• Efficiency of a Good But Not Linear Set Union Algorithm
• The Critical Points of a Function of n Variables
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• simpcomp
• A linear time algorithm for finding tree-decompositions of small treewidth
• Detecting genus in vertex links for the fast enumeration of 3-manifold triangulations
• Toward Optimality in Discrete Morse Theory
• Random Discrete Morse Theory and a New Library of Triangulations
• Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete
• The computational complexity of knot genus and spanning area
• Computing Optimal Morse Matchings
• Introducing Regina, The 3-Manifold Topology Software
• SOFSEM 2005: Theory and Practice of Computer Science
• Uniquely restricted matchings