Title: Collapsibility to a subcomplex of a given dimension is NP-complete,
Abstract: 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\geq 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\geq 3$). Our extended result,
together with the known polynomial-time algorithms for $(2,0)$ and $d=k+1$,
answers the question completely.