Collapsibility to a subcomplex of a given dimension is NP-complete

DOI10.1007/s00454-017-9915-6zbMath1380.05206arXiv1703.06983OpenAlexW2604403314MaRDI QIDQ1702356

Giovanni Paolini

Publication date: 28 February 2018

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

simplicial complexescollapsibilityNP-hardnessdiscrete Morse theory

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial aspects of simplicial complexes (05E45)

Uses Software

• Library of Triangulations

Cites Work

• Unnamed Item
• Morse theory for cell complexes
• A computationally intractable problem on simplicial complexes
• On discrete Morse functions and combinatorial decompositions
• Discrete Morse theory for cellular resolutions
• Parameterized Complexity of 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
• Computing Optimal Morse Matchings
• Combinatorial algebraic topology
• Recognition of collapsible complexes is NP-complete

This page was built for publication: Collapsibility to a subcomplex of a given dimension is NP-complete