Shellability is NP-complete Leibniz International Proceedings in Information, LIPIcs Goaoc, Xavier Paták, Pavel Patakova, Zuzana ; https://orcid.org/0000-0002-3975-1683 Tancer, Martin ; https://orcid.org/0000-0002-1191-6714 Wagner, Uli ; https://orcid.org/0000-0002-1494-0568 ddc:516 ddc:000 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. Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2018 info:eu-repo/semantics/conferenceObject doc-type:conferenceObject text http://purl.org/coar/resource_type/c_5794 https://research-explorer.ista.ac.at/record/184 https://research-explorer.ista.ac.at/download/184/5725 Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. Shellability is NP-complete. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018:41:1-41:16. doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2018.41">10.4230/LIPIcs.SoCG.2018.41</a> eng info:eu-repo/semantics/altIdentifier/doi/10.4230/LIPIcs.SoCG.2018.41 https://creativecommons.org/licenses/by/4.0/ info:eu-repo/semantics/openAccess