---
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.@eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Xavier
      foaf_name: Goaoc, Xavier
      foaf_surname: Goaoc
  - foaf_Person:
      foaf_givenName: Pavel
      foaf_name: Paták, Pavel
      foaf_surname: Paták
  - 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_workInfoHomepage: http://www.librecat.org/personId=38AC689C-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-1191-6714
  - 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.4230/LIPIcs.SoCG.2018.41
  bibo_volume: 99
  dct_date: 2018^xs_gYear
  dct_language: eng
  dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
  dct_title: Shellability is NP-complete@
...