Shellability is NP-complete - Archive ouverte HAL Access content directly
Journal Articles Journal of the ACM (JACM) Year : 2019

Shellability is NP-complete

(1) , (2) , (2) , (3) , (2)
1
2
3
Xavier Goaoc
Martin Tancer
• Function : Author

Abstract

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. Another simple corollary of our result is that it is NP-hard to decide whether a given poset is CL-shellable.

Dates and versions

hal-02050505 , version 1 (27-02-2019)

Identifiers

• HAL Id : hal-02050505 , version 1
• ARXIV :
• DOI :

Cite

Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, Uli Wagner. Shellability is NP-complete. Journal of the ACM (JACM), 2019, 66 (3), pp.1-18. ⟨10.1145/3314024⟩. ⟨hal-02050505⟩

56 View