Collapsibility to a subcomplex of a given dimension is NP-complete

Giovanni Paolini

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\ge k+2$ except $(2,0)$. By $(d,k)$-collapsibil…