Shellability is NP-complete

Xavier Goaoc, Pavel Paták, Zuzana Patáková +2

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 Dan…