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.
Journal of the ACM
Goaoc X, Patak P, Patakova Z, Tancer M, Wagner U. Shellability is NP-complete. Journal of the ACM. 2019;66(3). doi:10.1145/3314024
Goaoc, X., Patak, P., Patakova, Z., Tancer, M., & Wagner, U. (2019). Shellability is NP-complete. Journal of the ACM, 66(3). https://doi.org/10.1145/3314024
Goaoc, Xavier, Pavel Patak, Zuzana Patakova, Martin Tancer, and Uli Wagner. “Shellability Is NP-Complete.” Journal of the ACM 66, no. 3 (2019). https://doi.org/10.1145/3314024.
X. Goaoc, P. Patak, Z. Patakova, M. Tancer, and U. Wagner, “Shellability is NP-complete,” Journal of the ACM, vol. 66, no. 3, 2019.
Goaoc X, Patak P, Patakova Z, Tancer M, Wagner U. 2019. Shellability is NP-complete. Journal of the ACM. 66(3), 21.
Goaoc, Xavier, et al. “Shellability Is NP-Complete.” Journal of the ACM, vol. 66, no. 3, 21, ACM, 2019, doi:10.1145/3314024.
All files available under the following license(s):
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Material in IST: