论文标题
维度2中的计算PL几何类别的NP硬度
NP-hardness of computing PL geometric category in dimension 2
论文作者
论文摘要
多面体$ p $的PL几何类别，表示为$ \ hbox {plgcat}（p）$，为lusternik-schnirelmann类别提供了自然的上限，并将其定义为PL PL折叠折叠的最小数量，该折叠率coldapsible subpolyhedra cubpolyhedra of P $ $ p $ cover cover Pug $ p $。在维度2中，PL几何类别最多为〜3。很容易表征/识别$ 2 $ -POLYHEDRA $ P $，带有$ \ hbox {plgcat}（p）= 1 $。 Borghini提供了$ 2 $ -POLYHEDRA的部分特征，其中$ \ hbox {plgcat}（p）= 2 $。我们通过证明$ \ hbox {plgcat}（p）\ leq 2 $是NP-HARD来补充他的结果。因此，至少从算法意义上讲，我们不应该期望的是部分表征。我们的减少是基于这样的观察结果：二维Polyhedra $ p $承认可撒的子划分满足$ \ hbox {plgcat}（p）\ leq 2 $和（非平地）修改果阿克，Paták，paták，patáková，Tancer和Wagner is shellability obleslability obleslability obsshellability ob n $ 2 $ 2 $ -comcom-
The PL geometric category of a polyhedron $P$, denoted $\hbox{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 $\hbox{plgcat}(P) = 1$. Borghini provided a partial characterization of $2$-polyhedra with $\hbox{plgcat}(P) = 2$. We complement his result by showing that it is NP-hard to decide whether $\hbox{plgcat}(P)\leq 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 $\hbox{plgcat}(P) \leq 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.
