arXiv:1711.08436 [math.CO]AbstractReferencesReviewsResources
Shellability is NP-complete
Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, Uli Wagner
Published 2017-11-22Version 1
We prove that for every $d\geq 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 \ge 2$ and $k \ge 0$, deciding if a pure, $d$-dimensional, simplicial complex is $k$-decomposable is NP-hard. For $d \ge 3$, both problems remain NP-hard when restricted to contractible pure $d$-dimensional complexes.
Related articles: Most relevant | Search more
d-collapsibility is NP-complete for d greater or equal to 4
Subdivisions, shellability, and collapsibility of products
arXiv:1908.07155 [math.CO] (Published 2019-08-20)
Extendable shellability for $d$-dimensional complexes on $d+3$ vertices