2022/04/29 by Skotnica, Michael, Tancer, Martin
#Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Geometric Topology (math.GT)
paper · doi:10.48550/arxiv.2204.13981
The PL geometric category of a polyhedron P, denoted \hboxplgcat(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 \hboxplgcat(P) = 1. Borghini provided a partial characterization of 2-polyhedra with \hboxplgcat(P) = 2. We complement his result by showing that it is NP-hard to decide whether \hboxplgcat(P)≤ 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 \hboxplgcat(P) ≤ 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.