NP-hardness of computing PL geometric category in dimension 2

Abstract

The PL geometric category of a polyhedron $P$, denoted $plgcat(P)$, 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)\le 2$. Therefore, we should not expect much more than a partial characterization, at least in algorithmic sense. Our reduction is based on the observation that 2-dimensional polyhedra $P$ admitting a shellable subdivision satisfy $plgcat(P)\le 2$ and a (nontrivial) modification of the reduction of Goaoc, Paták, Patáková, Tancer and Wagner showing that shellability of $2$-complexes is NP-hard.

Version 2: 15 pages, 5 figures; typos corrected, a new figure explaining notions added