Abstract
The PL geometric category of a polyhedron P, denoted plgcat(P), is a combinatorial notion which provides a natural upper bound for the Lusternik--Schnirelmann category, and it is defined as the minimum number of PL collapsible subpolyhedra of P that cover P. In dimension 2 the PL geometric category is at most 3.
It is easy to characterize/recognize 2-polyhedra P with plgcat(P) = 1. Borghini provided a partial characterization of 2-polyhedra with plgcat(P) = 2.
We complement his result by showing that it is NP-hard to decide whether plgcat(P) <= 2. Therefore, we should not expect much more than a partial characterization, at least in an algorithmic sense.
Our reduction is based on the observation that 2-dimensional polyhedra P admitting a shellable subdivision satisfy plgcat(P) <= 2 and a (nontrivial) modification of the reduction of Goaoc, Patak, Patakova, Tancer and Wagner showing that shellability of 2-complexes is NP-hard.