Collapsibility to a Subcomplex of a Given Dimension is NP-Complete

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 d-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.