Shellability is NP-complete Conference Paper


Author(s): Goaoc, Xavier; Paták, Pavel; Patáková, Zuzana; Tancer, Martin; Wagner, Uli
Title: Shellability is NP-complete
Title Series: Leibniz International Proceedings in Information, LIPIcs
Affiliation IST Austria
Abstract: We prove that for every d ≥ 2, deciding if a pure, d-dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. 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, d-dimensional, simplicial complex is k-decomposable is NP-hard. For d ≥ 3, both problems remain NP-hard when restricted to contractible pure d-dimensional complexes.
Keywords: Simplicial complexes; NP Complete; shellability; NP-completeness; 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 - Leibniz-Zentrum für Informatik  
Date Published: 2018-06-11
Start Page: 411
End Page: 4116
Sponsor: Partially supported by the project EMBEDS II (CZ: 7AMB17FR029, FR: 38087RM) of Czech-French collaboration.
DOI: 10.4230/LIPIcs.SoCG.2018.41
Open access: yes (repository)
IST Austria Authors
  1. Uli Wagner
    50 Wagner
  2. Martin Tancer
    9 Tancer
Related IST Austria Work