arXiv Analytics

Sign in

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
arXiv:0808.1991 [math.CO] (Published 2008-08-14, updated 2010-06-23)
d-collapsibility is NP-complete for d greater or equal to 4
arXiv:1202.6606 [math.CO] (Published 2012-02-29, updated 2013-07-10)
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