Shellability is NP-complete

DOI10.1145/3314024zbMath1473.68198arXiv1711.08436OpenAlexW2949936695WikidataQ105336431 ScholiaQ105336431MaRDI QIDQ5215450

Pavel Paták, Martin Tancer, Zuzana Safernová, Xavier Goaoc, Uli Wagner

Publication date: 11 February 2020

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1711.08436

zbMATH Keywords

simplicial complexesNP-completenesscollapsibilityshellability

Mathematics Subject Classification ID

General topology of complexes (57Q05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial aspects of simplicial complexes (05E45) Computational aspects of digital topology (68U03)

Related Items (5)

New directions in real algebraic geometry. Abstracts from the workshop held March 19--24, 2023 ⋮ NP-Hardness of Computing PL Geometric Category in Dimension 2 ⋮ Shellable tilings on relative simplicial complexes and their \(h\)-vectors ⋮ Shellings and Sheddings Induced by Collapses ⋮ Shellings from relative shellings, with an application to NP-completeness

This page was built for publication: Shellability is NP-complete