Shellability Is Hard Even for Balls
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10476103" target="_blank" >RIV/00216208:11320/23:10476103 - isvavai.cz</a>
Alternative codes found
RIV/68407700:21240/23:00371167
Result on the web
<a href="https://doi.org/10.1145/3564246.3585152" target="_blank" >https://doi.org/10.1145/3564246.3585152</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1145/3564246.3585152" target="_blank" >10.1145/3564246.3585152</a>
Alternative languages
Result language
angličtina
Original language name
Shellability Is Hard Even for Balls
Original language description
The main goal of this paper is to show that shellability is NP-hard for triangulated d-balls (this also gives hardness for triangulated d-manifolds/d-pseudomanifolds with boundary) as soon as d >= 3. This extends our earlier work with Goaoc, Patakova and Wagner on hardness of shellability of 2-complexes and answers some questions implicitly raised by Danaraj and Klee in 1978 and explicitly mentioned by Santamaria-Galvis and Woodroofe. Together with the main goal, we also prove that collapsibility is NP-hard for 3-complexes embeddable in 3-space, extending an earlier work of the second author and answering an open question mentioned by Cohen, Fasy, Miller, Nayyeri, Peng andWalkington; and that shellability is NP-hard for 2-complexes embeddable in 3-space, answering another question of Santamaria-Galvis andWoodroofe (in a slightly stronger form than what is given by the main result).
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA22-19073S" target="_blank" >GA22-19073S: Combinatorial and computational complexity in topology and geometry</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
PROCEEDINGS OF THE 55TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2023
ISBN
978-1-4503-9913-5
ISSN
—
e-ISSN
—
Number of pages
14
Pages from-to
1271-1284
Publisher name
ASSOC COMPUTING MACHINERY
Place of publication
NEW YORK
Event location
Orlando
Event date
Jun 20, 2023
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
001064640700104