conference paper published yes Xavier Goaoc author Pavel Paták author Zuzana Patakova author 48B57058-F248-11E8-B48F-1D18A9856A870000-0002-3975-1683 Martin Tancer author 38AC689C-F248-11E8-B48F-1D18A9856A870000-0002-1191-6714 Uli Wagner author 36690CA2-F248-11E8-B48F-1D18A9856A870000-0002-1494-0568 UlWa department SoCG: Symposium on Computational Geometry 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. https://research-explorer.ista.ac.at/download/184/5725/2018_LIPIcs_Goaoc.pdf application/pdfno Schloss Dagstuhl - Leibniz-Zentrum für Informatik2018Budapest, Hungary eng 10.4230/LIPIcs.SoCG.2018.41 9941:1 - 41:16 https://research-explorer.ista.ac.at/record/7108 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> 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>. 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> 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. 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>. 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. 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. 1842018-12-11T11:45:04Z2025-06-04T07:49:02Z