NP-Hardness of Computing PL Geometric Category in Dimension 2

DOI10.1137/22M1523960MaRDI QIDQ6077977zbMATH OpenOpenAlexFDO

Authors Michael Skotnica, Martin Tancer

Publication date 27 September 2023

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2204.13981

zbMATH Keywords

collapsibleLusternik-Schnirelmann categoryNP-hardPL geometric categoryshellable

Mathematics Subject Classification ID

Combinatorial aspects of simplicial complexes (05E45) Lyusternik-Shnirel'man category of a space, topological complexity à la Farber, topological robotics (topological aspects) (55M30) Simple homotopy type, Whitehead torsion, Reidemeister-Franz torsion, etc. (57Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: 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)leq2$. 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)leq2$ and a (nontrivial) modification of the reduction of Goaoc, Pat'{a}k, Pat'{a}kov'{a}, Tancer and Wagner showing that shellability of $2$-complexes is NP-hard.

Recommendations

• \(P\) versus \(NP\) and geometry
• Complexity of PL manifolds
• scientific article; zbMATH DE number 1996521
• Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties
• Geometric complexity theory. I: An approach to the P vs. NP and related problems
• The complexity of the isomorphism problem for computable projective planes
• Complexity of geometric \(k\)-planarity for fixed \(k\)
• Complexity of some geometric and topological problems
• Complexity classes and completeness in algebraic geometry

Cites work

• Computational Complexity
• Decompositions of two-dimensional simplicial complexes
• Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete
• scientific article; zbMATH DE number 1819874 (Why is no real title available?)
• scientific article; zbMATH DE number 4102053 (Why is no real title available?)
• scientific article; zbMATH DE number 3749892 (Why is no real title available?)
• scientific article; zbMATH DE number 529110 (Why is no real title available?)
• scientific article; zbMATH DE number 1973373 (Why is no real title available?)
• scientific article; zbMATH DE number 2103273 (Why is no real title available?)
• scientific article; zbMATH DE number 3303053 (Why is no real title available?)
• Instabilities of robot motion
• On the topological complexity of aspherical spaces
• Recognition of collapsible complexes is NP-complete
• Shellability is NP-complete
• Shellings from relative shellings, with an application to NP-completeness
• Some remarks on PL collapsible covers of 2-dimensional polyhedra
• THE PROBLEM OF DISCRIMINATING ALGORITHMICALLY THE STANDARD THREE-DIMENSIONAL SPHERE
• Topological complexity of motion planning
• Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler

Cited in

(1)

• A note on the computational complexity of weak saturation

This page was built for publication: NP-Hardness of Computing PL Geometric Category in Dimension 2

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6077977)