Shellability is NP-complete

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.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/hal-02050505
Contributor : Xavier Goaoc <>
Submitted on : Wednesday, February 27, 2019 - 11:10:11 AM
Last modification on : Wednesday, April 3, 2019 - 1:23:16 AM

Links full text

Identifiers

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

Collections

Citation

Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, Uli Wagner. Shellability is NP-complete. Journal of the ACM (JACM), Association for Computing Machinery, In press. ⟨hal-02050505⟩

Share

Metrics

Record views

37