Back to Search
Start Over
NP-HARDNESS OF COMPUTING PL GEOMETRIC CATEGORY IN DIMENSION 2.
- Source :
-
SIAM Journal on Discrete Mathematics . 2023, Vol. 37 Issue 3, p2016-2029. 14p. - Publication Year :
- 2023
-
Abstract
- The PL geometric category of a polyhedron P, denoted plgcat(P), 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 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) ≤ 2. 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 P admitting a shellable subdivision satisfy plgcat(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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *NP-hard problems
*POLYHEDRA
*SENSES
*SUBDIVISION surfaces (Geometry)
Subjects
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 37
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 173328554
- Full Text :
- https://doi.org/10.1137/22M1523960