Recognizing shrinkable complexes is NP-complete

Dominique Attali, Olivier Devillers, Marc Glisse, Sylvain Lazard


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.

Full Text:

PDF Model


ISSN: 1920-180X