Shellability is NP-complete
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.
READ FULL TEXT