Shellability is NP-complete

DOI10.4230/LIPICS.SOCG.2018.41MaRDI QIDQ5115809zbMATHFDO

Authors Xavier Goaoc, Pavel Paták, Zuzana Safernova, Martin Tancer, Uli Wagner

Publication date 18 August 2020

zbMATH Keywords

simplicial complexesNP-completenessshellabilitycollapsibility

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) General topology of complexes (57Q05) Combinatorial aspects of simplicial complexes (05E45) Computational aspects of digital topology (68U03)

Recommendations

• Shellability is NP-complete
• Shellings from relative shellings, with an application to NP-completeness
• Recognizing shrinkable complexes is NP-complete
• Recognizing shrinkable complexes is NP-complete
• Recognition of collapsible complexes is NP-complete

Cites work

• scientific article; zbMATH DE number 3850090 (Why is no real title available?)
• scientific article; zbMATH DE number 3749892 (Why is no real title available?)
• scientific article; zbMATH DE number 1961535 (Why is no real title available?)
• scientific article; zbMATH DE number 863503 (Why is no real title available?)
• A Representation of 2-dimensional Pseudomanifolds and its use in the Design of a Linear-Time Shelling Algorithm
• A computationally intractable problem on simplicial complexes
• Bruhat order of Coxeter groups and shellability
• Combinatorics and commutative algebra.
• Computational Complexity
• Computing Optimal Morse Matchings
• Convex Polytopes
• Decompositions of Simplicial Complexes Related to Diameters of Convex Polyhedra
• Decompositions of two-dimensional simplicial complexes
• Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete
• Einstein structures: Existence versus uniqueness
• How to shell a monoid
• On Lexicographically Shellable Posets
• On the shellability of the order complex of the subgroup lattice of a finite group
• Optimal discrete Morse functions for 2-manifolds
• Poset topology: tools and applications
• Recognition of collapsible complexes is NP-complete
• Recognizing shrinkable complexes is NP-complete
• Shellability is NP-complete
• Shellable Decompositions of Cells and Spheres.
• Shellable and Cohen-Macaulay Partially Ordered Sets
• Shellable nonpure complexes and posets. II
• Shellings of spheres and polytopes
• THE PROBLEM OF DISCRIMINATING ALGORITHMICALLY THE STANDARD THREE-DIMENSIONAL SPHERE
• The maximum numbers of faces of a convex polytope
• Which Spheres are Shellable?

Cited in

(13)

• Shellability is NP-complete
• Decomposable clutters and a generalization of Simon's conjecture
• LaserTank is NP-Complete
• scientific article; zbMATH DE number 1860710 (Why is no real title available?)
• \(h\)-assignments of simplicial complexes and reverse search
• Counting shellings of complete bipartite graphs and trees
• \(d\)-collapsibility is NP-complete for \(d \geq 4\)
• Hyperplane Neural Codes and the Polar Complex
• Shellability is NP-complete
• \(D\)-collapsibility is NP-complete for \(d \geq 4\)
• Shellings from relative shellings, with an application to NP-completeness
• Recognizing shrinkable complexes is NP-complete
• Recognizing shrinkable complexes is NP-complete

This page was built for publication: Shellability is NP-complete

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