NP-Hardness of Computing PL Geometric Category in Dimension 2
Michael Skotnica, Martin Tancer · SIAM Journal on Discrete Mathematics · 2023
Abstract. The PL geometric category of a polyhedron [Formula: see text], denoted [Formula: see text], 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 [Formula: see text] that cover [Formula: see text]. In dimension 2 the PL geometric category is at most 3. It is easy to characterize/recognize 2-polyhedra [Formula: see text] with [Formula: see text]. Borghini provided a partial characterization of 2-polyhedra with [Formula: see text]. We complement his result by showing that it is NP-hard to decide whether [Formula: see text]. 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 [Formula: see text] admitting a shellable subdivision satisfy [Formula: see text] 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.