Published 2016 | Version v1
Journal article

Recognizing Shrinkable Complexes Is NP-Complete

Contributors

Others:

Description

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.

Abstract

International audience

Additional details

Identifiers

URL
https://hal.inria.fr/hal-01384396
URN
urn:oai:HAL:hal-01384396v2

Origin repository

Origin repository
UNICA