Recognition of collapsible complexes is NP-complete

2012/11/27 by Tancer, Martin · 2 citations
#05E45 #68Q17 #Computational Geometry (cs.CG) #F.2.2 #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1211.6254

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.

Cited by

• Leader Election via Unique Sink Orientation
• Minimal Unimodal Decomposition is NP-Hard on Graphs

Related

• d-collapsibility is NP-complete for d greater or equal to 4
• The threshold for collapsibility in random complexes
• The collapsibility of some CAT(0) simplicial complexes of dimension 3
• A note on collapsibility of acyclic 2-complexes
• Shellability is NP-complete