Recognizing Shrinkable Complexes Is NP-Complete

Dominique Attali 1 Olivier Devillers 2 Marc Glisse 3 Sylvain Lazard 2
1 GIPSA-AGPIG - AGPIG
GIPSA-DIS - Département Images et Signal
2 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
3 DATASHAPE - Understanding the Shape of Data
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download

vignette.jpg
vignette.jpg
https://hal.inria.fr/hal-01384396
Contributor : Olivier Devillers <>
Submitted on : Monday, March 5, 2018 - 11:01:46 AM
Last modification on : Friday, September 20, 2019 - 4:56:35 PM

Files

jocg.pdf
Files produced by the author(s)

Identifiers

Collections

UGA | UNIV-LORRAINE | LORIA | LORIA-ALGO | UNIV-PARIS-SACLAY | GIPSA-AGPIG | INRIA | GIPSA | UNIV-COTEDAZUR | GIPSA-DIS

Citation

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

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

924

Files downloads

548

Contact


archive-ouverte@inria.fr