Recognition of Collapsible Complexes is NP-Complete
Recognition of Collapsible Complexes is NP-Complete
复制标题
DOI：
10.1007/s00454-015-9747-1
复制
发表时间：
2012-11
影响因子：
0.8
通讯作者：
M. Tancer
中科院分区：
文献类型：
--
作者：
M. Tancer
我们证明，决定给定的（3 维）单纯复形是否可折叠是 NP 完全的。这项工作扩展了 Malgouyres 和 Francés 的结果，表明决定给定的单纯复形是否塌陷为 1-复形是 NP 完全的。
We prove that it is NP-complete to decide whether a given (3-dimensional) simplicial complex is collapsible. This work extends a result of Malgouyres and Francés showing that it is NP-complete to decide whether a given simplicial complex collapses to a 1-complex.