Recognizing shrinkable complexes is NP-complete

Dominique Attali 1 Olivier Devillers 2 Marc Glisse 2 Sylvain Lazard 3
1 GIPSA-AGPIG - AGPIG
GIPSA-DIS - Département Images et Signal
2 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
3 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
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 (three-dimensional) simplicial complex is shrinkable. Along the way, we describe examples of contractible complexes which are not shrinkable.
Document type :
Conference papers
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download


https://hal.inria.fr/hal-01015747
Contributor : Olivier Devillers <>
Submitted on : Friday, June 27, 2014 - 9:45:30 AM
Last modification on : Tuesday, June 18, 2019 - 2:36:02 PM
Long-term archiving on : Saturday, September 27, 2014 - 10:50:38 AM

Files

esa.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01015747, version 1

Citation

Dominique Attali, Olivier Devillers, Marc Glisse, Sylvain Lazard. Recognizing shrinkable complexes is NP-complete. 22nd European Symposium on Algorithms, 2014, Wroclaw, Poland. pp.74-86. ⟨hal-01015747⟩

Share

Metrics

Record views

1231

Files downloads

545