--- res: bibo_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.@eng bibo_authorlist: - foaf_Person: foaf_givenName: Xavier foaf_name: Goaoc, Xavier foaf_surname: Goaoc - foaf_Person: foaf_givenName: Pavel foaf_name: Paták, Pavel foaf_surname: Paták - foaf_Person: foaf_givenName: Zuzana foaf_name: Patakova, Zuzana foaf_surname: Patakova foaf_workInfoHomepage: http://www.librecat.org/personId=48B57058-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0002-3975-1683 - foaf_Person: foaf_givenName: Martin foaf_name: Tancer, Martin foaf_surname: Tancer foaf_workInfoHomepage: http://www.librecat.org/personId=38AC689C-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0002-1191-6714 - foaf_Person: foaf_givenName: Uli foaf_name: Wagner, Uli foaf_surname: Wagner foaf_workInfoHomepage: http://www.librecat.org/personId=36690CA2-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0002-1494-0568 bibo_doi: 10.4230/LIPIcs.SoCG.2018.41 bibo_volume: 99 dct_date: 2018^xs_gYear dct_language: eng dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@ dct_title: Shellability is NP-complete@ ...