{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T08:23:00Z","timestamp":1782289380522,"version":"3.54.5"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,6,14]],"date-time":"2019-06-14T00:00:00Z","timestamp":1560470400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100014988","name":"IST Austria","doi-asserted-by":"crossref","award":["CZ.02.2.69\/0.0\/0.0\/17_050\/0008466"],"award-info":[{"award-number":["CZ.02.2.69\/0.0\/0.0\/17_050\/0008466"]}],"id":[{"id":"10.13039\/100014988","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Czech-French collaboration project EMBEDS II","award":["CZ: 7AMB17FR029, and FR: 38087RM"],"award-info":[{"award-number":["CZ: 7AMB17FR029, and FR: 38087RM"]}]},{"name":"Charles University project","award":["UNCE\/SCI\/004"],"award-info":[{"award-number":["UNCE\/SCI\/004"]}]},{"DOI":"10.13039\/501100001824","name":"GA\u010cR","doi-asserted-by":"crossref","award":["16-01602Y"],"award-info":[{"award-number":["16-01602Y"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Improvement of Internationalization in the Field of Research and Development at Charles University"},{"name":"IUF. M. Tancer"},{"name":"MSCA-IF"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,6,30]]},"abstract":"<jats:p>\n            We prove that for every\n            <jats:italic>d<\/jats:italic>\n            \u2265 2, deciding if a pure,\n            <jats:italic>d<\/jats:italic>\n            -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\n            <jats:italic>d<\/jats:italic>\n            \u2265 2 and\n            <jats:italic>k<\/jats:italic>\n            \u2265 0, deciding if a pure,\n            <jats:italic>d<\/jats:italic>\n            -dimensional, simplicial complex is\n            <jats:italic>k<\/jats:italic>\n            -decomposable is NP-hard. For\n            <jats:italic>d<\/jats:italic>\n            \u2265 3, both problems remain NP-hard when restricted to contractible pure\n            <jats:italic>d<\/jats:italic>\n            -dimensional complexes. Another simple corollary of our result is that it is NP-hard to decide whether a given poset is CL-shellable.\n          <\/jats:p>","DOI":"10.1145\/3314024","type":"journal-article","created":{"date-parts":[[2019,6,17]],"date-time":"2019-06-17T12:56:40Z","timestamp":1560776200000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Shellability is NP-complete"],"prefix":"10.1145","volume":"66","author":[{"given":"Xavier","family":"Goaoc","sequence":"first","affiliation":[{"name":"Universit\u00e9 de Lorraine, CNRS, INRIA, LORIA F-54000, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pavel","family":"Pat\u00e1k","sequence":"additional","affiliation":[{"name":"IST Austria, Austria and Department of Applied Mathematics, Charles University, Czech Republic"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zuzana","family":"Pat\u00e1kov\u00e1","sequence":"additional","affiliation":[{"name":"IST Austria, Austria and Computer Science Institute, Charles University, Czech Republic"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Tancer","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics, Charles University, Czech Republic"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1494-0568","authenticated-orcid":false,"given":"Uli","family":"Wagner","sequence":"additional","affiliation":[{"name":"IST Austria, Klosterneuburg, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,6,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1540612"},{"key":"e_1_2_1_2_1","first-page":"430","article-title":"Recognizing shrinkable complexes is NP-complete","volume":"7","author":"Attali D.","year":"2016","unstructured":"D. Attali , O. Devillers , M. Glisse , and S. Lazard . 2016 . Recognizing shrinkable complexes is NP-complete . Journal of Computational Geometry 7 , 1 (2016), 430 -- 443 . D. Attali, O. Devillers, M. Glisse, and S. Lazard. 2016. Recognizing shrinkable complexes is NP-complete. Journal of Computational Geometry 7, 1 (2016), 430--443.","journal-title":"Journal of Computational Geometry"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1090\/coll\/040"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.2307\/1999881"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/233228.233246"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(82)90029-9"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.2307\/1999359"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-97-01838-2"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.7146\/math.scand.a-11045"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-74-04150-7"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70321-2"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70320-0"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00015-1"},{"key":"e_1_2_1_14_1","volume-title":"Graduate Texts in Mathematics","author":"Gr\u00fcnbaum B.","unstructured":"B. Gr\u00fcnbaum . 2003. Convex Polytopes (2 ed.). Graduate Texts in Mathematics , Vol. 221 . Springer-Verlag , New York . xvi+468 pages. Prepared and with a preface by Volker Kaibel, Victor Klee and G\u00fcnter M. Ziegler. B. Gr\u00fcnbaum. 2003. Convex Polytopes (2 ed.). Graduate Texts in Mathematics, Vol. 221. Springer-Verlag, New York. xvi+468 pages. Prepared and with a preface by Volker Kaibel, Victor Klee and G\u00fcnter M. Ziegler."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2006.10.023"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480104445885"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"V. Kaibel and M. E. Pfetsch. 2003. Some algorithmic problems in polytope theory. In Algebra Geometry and Software Systems. Springer Berlin 23--47.  V. Kaibel and M. E. Pfetsch. 2003. Some algorithmic problems in polytope theory. In Algebra Geometry and Software Systems. Springer Berlin 23--47.","DOI":"10.1007\/978-3-662-05148-1_2"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(03)00014-2"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1792454.1792474"},{"key":"e_1_2_1_21_1","volume-title":"Using the Borsuk-Ulam Theorem","author":"Matou\u0161ek J.","unstructured":"J. Matou\u0161ek . 2007. Using the Borsuk-Ulam Theorem . Springer-Verlag , Berlin . J. Matou\u0161ek. 2007. Using the Borsuk-Ulam Theorem. Springer-Verlag, Berlin."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300002850"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01928216"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002080050152"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.5.4.576"},{"key":"e_1_2_1_26_1","unstructured":"C. P. Rourke and B. J. Sanderson. 1982. Introduction to Piecewise-Linear Topology. Springer-Verlag Berlin-New York. viii+123 pages. Reprint.  C. P. Rourke and B. J. Sanderson. 1982. Introduction to Piecewise-Linear Topology. Springer-Verlag Berlin-New York. viii+123 pages. Reprint."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-01-02730-1"},{"key":"e_1_2_1_28_1","volume-title":"Combinatorics and Commutative Algebra (2 ed.). Progress in Mathematics","author":"Stanley R. P.","unstructured":"R. P. Stanley . 1996. Combinatorics and Commutative Algebra (2 ed.). Progress in Mathematics , Vol. 41 . Birkh\u00e4user Boston, Inc. , Boston, MA . x+164 pages. R. P. Stanley. 1996. Combinatorics and Commutative Algebra (2 ed.). Progress in Mathematics, Vol. 41. Birkh\u00e4user Boston, Inc., Boston, MA. x+164 pages."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-015-9747-1"},{"key":"e_1_2_1_30_1","first-page":"71","article-title":"The problem of discriminating algorithmically the standard three-dimensional sphere","volume":"29","author":"Volodin I. A.","year":"1974","unstructured":"I. A. Volodin , V. E. Kuznetsov , and A. T. Fomenko . 1974 . The problem of discriminating algorithmically the standard three-dimensional sphere . Uspekhi Matematicheskikh Nauk 29 , 5 (1974), 71 -- 168 . In Russian. English translation: Russian Mathematical Surveys 29, 5 (1974), 71--172. I. A. Volodin, V. E. Kuznetsov, and A. T. Fomenko. 1974. The problem of discriminating algorithmically the standard three-dimensional sphere. Uspekhi Matematicheskikh Nauk 29, 5 (1974), 71--168. In Russian. English translation: Russian Mathematical Surveys 29, 5 (1974), 71--172.","journal-title":"Uspekhi Matematicheskikh Nauk"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1090\/pcms\/013\/09"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-45.1.243"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3314024","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3314024","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:47Z","timestamp":1750202627000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3314024"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,14]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,6,30]]}},"alternative-id":["10.1145\/3314024"],"URL":"https:\/\/doi.org\/10.1145\/3314024","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,14]]},"assertion":[{"value":"2018-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}