2017/11/22 by Xavier Goaoc, Pavel Paták, Goaoc, Xavier +7 · 3 citations
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Geometric Topology (math.GT) #cs.CG #math.CO #math.GT
paper · pdf · doi:10.48550/arxiv.1711.08436
Version 2: 17 pages, 11 figures. Improved readability at various places. Proof in Section 6 simplified
arxiv created 2018/01/24 · arxiv updated 2018/01/26
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. Another simple corollary of our result is that it is NP-hard to decide whether a given poset is CL-shellable.