[2204.13981] NP hardness of computation of PL geometric category in dimension 2

Download the PDF of the paper entitled NP-hardness of Computation of PL Geometric Categories in Dimension 2 by Michael Skotnica and Martin Tancer.

Download PDF

overview: The PL geometric category of the polyhedron $P$ denoted by $\hbox{plgcat}(P)$ provides a natural upper bound for the Lusternik-Schnirelmann category, and as the minimum number of PL-foldable subpolyhedra of $P Defined. $ covering $P$. In dimension 2, the PL geometric categories are ~3 at most. It is easy to characterize/recognize the $2$-polyhedron $P$ with $\hbox{plgcat}(P) = 1$. Borghini provided a partial characterization of the $2$-polyhedron with $\hbox{plgcat}(P) = 2$. I supplement his result by showing that he is NP-hard to decide whether $\hbox{plgcat}(P)\leq2$. So you shouldn’t expect anything more than partial characterization, at least in an algorithmic sense. Our reduction is based on the observation that the two-dimensional polyhedron $P$ admits shellable subdivisions, $\hbox{plgcat}(P) \leq 2$ and Goaoc, Paták, Patáková and Tancer’s Satisfies the (non-trivial) fix for reduction. and Wagner show that the $2$- complex sherability is his NP-hard.