Shellability is NP-complete
Goaoc, Xavier
Patak, Pavel
Patakova, Zuzana
Tancer, Martin
Wagner, Uli
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.
ACM
2019
info:eu-repo/semantics/article
doc-type:article
text
https://research-explorer.app.ist.ac.at/record/7108
Goaoc X, Patak P, Patakova Z, Tancer M, Wagner U. Shellability is NP-complete. <i>Journal of the ACM</i>. 2019;66(3). doi:<a href="https://doi.org/10.1145/3314024">10.1145/3314024</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1145/3314024
info:eu-repo/semantics/altIdentifier/issn/0004-5411
info:eu-repo/semantics/altIdentifier/arxiv/1711.08436
info:eu-repo/semantics/openAccess