---
res:
bibo_abstract:
- 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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Xavier
foaf_name: Goaoc, Xavier
foaf_surname: Goaoc
- foaf_Person:
foaf_givenName: Pavel
foaf_name: Patak, Pavel
foaf_surname: Patak
foaf_workInfoHomepage: http://www.librecat.org/personId=B593B804-1035-11EA-B4F1-947645A5BB83
- foaf_Person:
foaf_givenName: Zuzana
foaf_name: Patakova, Zuzana
foaf_surname: Patakova
foaf_workInfoHomepage: http://www.librecat.org/personId=48B57058-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-3975-1683
- foaf_Person:
foaf_givenName: Martin
foaf_name: Tancer, Martin
foaf_surname: Tancer
- foaf_Person:
foaf_givenName: Uli
foaf_name: Wagner, Uli
foaf_surname: Wagner
foaf_workInfoHomepage: http://www.librecat.org/personId=36690CA2-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-1494-0568
bibo_doi: 10.1145/3314024
bibo_issue: '3'
bibo_volume: 66
dct_date: 2019^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0004-5411
dct_language: eng
dct_publisher: ACM@
dct_title: Shellability is NP-complete@
...