Skip to Main content Skip to Navigation
New interface
Conference papers

Recognizing shrinkable complexes is NP-complete

Dominique Attali 1 Olivier Devillers 2 Marc Glisse 2 Sylvain Lazard 3 
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 metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Friday, June 27, 2014 - 9:45:30 AM
Last modification on : Friday, January 21, 2022 - 3:10:57 AM
Long-term archiving on: : Saturday, September 27, 2014 - 10:50:38 AM


Files produced by the author(s)



Dominique Attali, Olivier Devillers, Marc Glisse, Sylvain Lazard. Recognizing shrinkable complexes is NP-complete. ESA 2014 - 22nd Annual European Symposium on Algorithms, Sep 2014, Wroclaw, Poland. pp.74-86, ⟨10.1007/978-3-662-44777-2_7⟩. ⟨hal-01015747⟩



Record views


Files downloads