Shellability is NP-complete

Abstract

We prove that for every $d\ge 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. Another simple corollary of our result is that it is NP-hard to decide whether a given poset is CL-shellable.

Version 2: 17 pages, 11 figures. Improved readability at various places. Proof in Section 6 simplified