Shellability is NP-complete

X. Goaoc, P. Patak, Z. Patakova, M. Tancer, U. Wagner, Journal of the ACM 66 (2019).


Journal Article | Published | English
Department
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.
Publishing Year
Date Published
2019-06-01
Journal Title
Journal of the ACM
Volume
66
Issue
3
Article Number
21
ISSN
IST-REx-ID

Cite this

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.

Link(s) to Main File(s)
Access Level
OA Open Access
Material in IST:
Earlier Version

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1711.08436

Search this title in

Google Scholar