@article{7108,
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. Another simple corollary of our result is that it is NP-hard to decide whether a given poset is CL-shellable.},
author = {Goaoc, Xavier and Patak, Pavel and Patakova, Zuzana and Tancer, Martin and Wagner, Uli},
issn = {0004-5411},
journal = {Journal of the ACM},
number = {3},
publisher = {ACM},
title = {{Shellability is NP-complete}},
doi = {10.1145/3314024},
volume = {66},
year = {2019},
}