Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2211.07978 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929435864727552 |
|---|---|
| author | Paták, Pavel Tancer, Martin |
| author_facet | Paták, Pavel Tancer, Martin |
| contents | 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 is at least 3. This extends our earlier work with Goaoc, Patáková 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 Santamaría-Galvis and Woodroofe. Together with the main goal, we also prove that collapsibility is NP-hard for 3-complexes embeddable in the 3-space, extending an earlier work of the second author and answering an open question mentioned by Cohen, Fasy, Miller, Nayyeri, Peng and Walkington; and that shellability is NP-hard for 2-complexes embeddable in the 3-space, answering another question of Santamaría-Galvis and Woodroofe (in a slightly stronger form than what is given by the main result). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_07978 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Shellability is hard even for balls Paták, Pavel Tancer, Martin Computational Geometry Combinatorics Geometric Topology 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 is at least 3. This extends our earlier work with Goaoc, Patáková 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 Santamaría-Galvis and Woodroofe. Together with the main goal, we also prove that collapsibility is NP-hard for 3-complexes embeddable in the 3-space, extending an earlier work of the second author and answering an open question mentioned by Cohen, Fasy, Miller, Nayyeri, Peng and Walkington; and that shellability is NP-hard for 2-complexes embeddable in the 3-space, answering another question of Santamaría-Galvis and Woodroofe (in a slightly stronger form than what is given by the main result). |
| title | Shellability is hard even for balls |
| topic | Computational Geometry Combinatorics Geometric Topology |
| url | https://arxiv.org/abs/2211.07978 |