10.1145/3314024
Goaoc, Xavier
Xavier
Goaoc
Patak, Pavel
Pavel
Patak
Patakova, Zuzana
Zuzana
Patakova0000-0002-3975-1683
Tancer, Martin
Martin
Tancer
Wagner, Uli
Uli
Wagner0000-0002-1494-0568
Shellability is NP-complete
ACM
2019
2019-11-26T10:13:59Z
2020-01-21T12:05:56Z
journal_article
https://research-explorer.app.ist.ac.at/record/7108
https://research-explorer.app.ist.ac.at/record/7108.json
0004-5411
1711.08436
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.