Recognition of collapsible complexes is NP-complete

Abstract

We prove that it is NP-complete to decide whether a given (3-dimensional) simplicial complex is collapsible. This work extends a result of Malgouyres and Francés showing that it is NP-complete to decide whether a given simplicial complex collapses to a 1-complex.

21 pages, 13 figures (Appendix was reworked in version v2. Other changes are mainly in the introduction + numerous minor fixes.)

Cited by in corpus (4)

• Parameterized Complexity of Discrete Morse Theory
• Strong Collapse for Persistence
• Hardness of Approximation for Morse Matching
• Linear embeddings of contractible and collapsible complexes