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

In this paper we extend the works of Tancer and of 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.