In this paper we extend the works of Tancer, Malgouyres and Francés, showing that (d, k)-Collapsibility is NP-complete for d ≥ k + 2 except (2, 0). By
(d, k)-Collapsibility we mean the following problem: determine whether a given dimensional simplicial complex can be collapsed to some k-dimensional subcomplex. The question of establishing the complexity status of (d, k)-Collapsibility was asked by Tancer, who proved NP-completeness of (d, 0) and (d, 1)-Collapsibility (for d ≥ 3). Our extended result, together with the known polynomial-time algorithms for (2, 0) and d = k + 1, answers the question completely.

EB00000003315K

Available