Recognizing shrinkable complexes is NP-complete
Dominique Attali, Olivier Devillers, Marc Glisse, Sylvain Lazard · Journal of Computational Geometry (Carleton University) · 2016
We say that a simplicial complex is "shrinkable" if there exists a sequence of admissible edge contractions that reduces the complex to a single vertex. We prove that it is NP-complete to decide whether a (two-dimensional) simplicial complex is shrinkable. Along the way, we describe examples of contractible complexes that are not shrinkable.