Recognizing shrinkable complexes is NP-complete

Dominique Attali, Olivier Devillers, Marc Glisse, Sylvain Lazard

Abstract


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


DOI: http://dx.doi.org/10.20382/jocg.v7i1a18

ISSN: 1920-180X