---
_id: '184'
abstract:
- lang: eng
  text: 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.
acknowledgement: 'Partially supported by the project EMBEDS II (CZ: 7AMB17FR029, FR:
  38087RM) of Czech-French collaboration.'
alternative_title:
- Leibniz International Proceedings in Information, LIPIcs
author:
- first_name: Xavier
  full_name: Goaoc, Xavier
  last_name: Goaoc
- first_name: Pavel
  full_name: Paták, Pavel
  last_name: Paták
- first_name: Zuzana
  full_name: Patakova, Zuzana
  id: 48B57058-F248-11E8-B48F-1D18A9856A87
  last_name: Patakova
  orcid: 0000-0002-3975-1683
- first_name: Martin
  full_name: Tancer, Martin
  id: 38AC689C-F248-11E8-B48F-1D18A9856A87
  last_name: Tancer
  orcid: 0000-0002-1191-6714
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
citation:
  ama: 'Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. Shellability is NP-complete.
    In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018:41:1-41:16.
    doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2018.41">10.4230/LIPIcs.SoCG.2018.41</a>'
  apa: 'Goaoc, X., Paták, P., Patakova, Z., Tancer, M., &#38; Wagner, U. (2018). Shellability
    is NP-complete (Vol. 99, p. 41:1-41:16). Presented at the SoCG: Symposium on Computational
    Geometry, Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
    <a href="https://doi.org/10.4230/LIPIcs.SoCG.2018.41">https://doi.org/10.4230/LIPIcs.SoCG.2018.41</a>'
  chicago: Goaoc, Xavier, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner.
    “Shellability Is NP-Complete,” 99:41:1-41:16. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2018. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2018.41">https://doi.org/10.4230/LIPIcs.SoCG.2018.41</a>.
  ieee: 'X. Goaoc, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “Shellability
    is NP-complete,” presented at the SoCG: Symposium on Computational Geometry, Budapest,
    Hungary, 2018, vol. 99, p. 41:1-41:16.'
  ista: 'Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. 2018. Shellability is NP-complete.
    SoCG: Symposium on Computational Geometry, Leibniz International Proceedings in
    Information, LIPIcs, vol. 99, 41:1-41:16.'
  mla: Goaoc, Xavier, et al. <i>Shellability Is NP-Complete</i>. Vol. 99, Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 41:1-41:16, doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2018.41">10.4230/LIPIcs.SoCG.2018.41</a>.
  short: X. Goaoc, P. Paták, Z. Patakova, M. Tancer, U. Wagner, in:, Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik, 2018, p. 41:1-41:16.
conference:
  end_date: 2018-06-14
  location: Budapest, Hungary
  name: 'SoCG: Symposium on Computational Geometry'
  start_date: 2018-06-11
date_created: 2018-12-11T11:45:04Z
date_published: 2018-06-11T00:00:00Z
date_updated: 2025-06-04T07:49:02Z
day: '11'
ddc:
- '516'
- '000'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2018.41
file:
- access_level: open_access
  checksum: d12bdd60f04a57307867704b5f930afd
  content_type: application/pdf
  creator: dernst
  date_created: 2018-12-17T16:35:02Z
  date_updated: 2020-07-14T12:45:18Z
  file_id: '5725'
  file_name: 2018_LIPIcs_Goaoc.pdf
  file_size: 718414
  relation: main_file
file_date_updated: 2020-07-14T12:45:18Z
has_accepted_license: '1'
intvolume: '        99'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 41:1 - 41:16
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '7736'
quality_controlled: '1'
related_material:
  record:
  - id: '7108'
    relation: later_version
    status: public
scopus_import: 1
status: public
title: Shellability is NP-complete
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 99
year: '2018'
...