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.
https://hal.inria.fr/hal-01384396
Contributor : Olivier Devillers
<>
Submitted on : Monday, March 5, 2018 - 11:01:46 AM
Last modification on : Tuesday, June 18, 2019 - 2:36:02 PM
