@inproceedings{184,
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.},
author = {Goaoc, Xavier and Paták, Pavel and Patakova, Zuzana and Tancer, Martin and Wagner, Uli},
location = {Budapest, Hungary},
pages = {41:1 -- 41:16},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Shellability is NP-complete}},
doi = {10.4230/LIPIcs.SoCG.2018.41},
volume = {99},
year = {2018},
}