Author(s):

Goaoc, Xavier; Paták, Pavel; Patáková, Zuzana; Tancer, Martin; Wagner, Uli

Title: 
Shellability is NPcomplete

Title Series: 
Leibniz International Proceedings in Information, LIPIcs

Affiliation 
IST Austria 
Abstract: 
We prove that for every d ≥ 2, deciding if a pure, ddimensional, simplicial complex is shellable is NPhard, hence NPcomplete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every d ≥ 2 and k ≥ 0, deciding if a pure, ddimensional, simplicial complex is kdecomposable is NPhard. For d ≥ 3, both problems remain NPhard when restricted to contractible pure ddimensional complexes.

Keywords: 
Simplicial complexes; NP Complete; shellability; NPcompleteness; Collapsibility

Conference Title:

SoCG: Symposium on Computational Geometry

Volume: 
99

Conference Dates:

June 11  14, 2018

Conference Location:

Budapest, Hungary

ISBN:

18688969 (ISSN); 9783959770668 (ISBN)

Publisher:

Schloss Dagstuhl  LeibnizZentrum für Informatik

Date Published:

20180611

Start Page: 
411

End Page:

4116

Sponsor: 
Partially supported by the project EMBEDS II (CZ: 7AMB17FR029, FR: 38087RM) of CzechFrench collaboration.

DOI: 
10.4230/LIPIcs.SoCG.2018.41

Open access: 
yes (repository) 