Recognizing Shrinkable Complexes Is NP-Complete

Dominique Attali (1) , Olivier Devillers (2) , Marc Glisse (3) , Sylvain Lazard (2)

1 GIPSA-AGPIG - GIPSA - Architecture, Géométrie, Perception, Images, Gestes
2 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
3 DATASHAPE - Understanding the Shape of Data

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.

Domaines: Géométrie algorithmique [cs.CG]

Dominique Attali, Olivier Devillers, Marc Glisse, Sylvain Lazard. Recognizing Shrinkable Complexes Is NP-Complete. Journal of Computational Geometry, 2016, 7 (1), pp.430--443. ⟨10.20382/jocg.v7i1a18⟩. ⟨hal-01384396v2⟩