Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete

DOI10.1007/978-3-540-79126-3_17MaRDI QIDQ5458885zbMATH OpenOpenAlexFDO

Authors Rémy Malgouyres, A. R. Francés

Publication date 24 April 2008

Published in Discrete Geometry for Computer Imagery (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-79126-3_17

zbMATH Keywords

CollapsingComputational ComplexityNP-completenessSimplicial Topology

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Collapsibility to a subcomplex of a given dimension is NP-complete
• Recognition of collapsible complexes is NP-complete
• Recognising a partitionable simplicial complex is in \(\text{NP}\)
• Recognizing shrinkable complexes is NP-complete
• Recognizing shrinkable complexes is NP-complete
• Collapsibility of simplicial complexes of hypergraphs
• A computationally intractable problem on simplicial complexes
• d-collapsibility is NP-complete for d 4
• D-collapsibility is NP-complete for d 4
• Embeddability of Simplicial Complexes is Undecidable

Cites work

• A computationally intractable problem on simplicial complexes
• A concise characterization of 3D simple points
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1104449 (Why is no real title available?)
• scientific article; zbMATH DE number 1142309 (Why is no real title available?)
• scientific article; zbMATH DE number 3205926 (Why is no real title available?)
• The complexity of theorem-proving procedures

Cited in

(21)

• Collapsibility to a subcomplex of a given dimension is NP-complete
• A computationally intractable problem on simplicial complexes
• Shellings from relative shellings, with an application to NP-completeness
• Frontiers of sphere recognition in practice
• Powerful parallel and symmetric 3D thinning schemes based on critical kernels
• Searching combinatorial optimality using graph-based homology information
• D-collapsibility is NP-complete for d 4
• Recognizing shrinkable complexes is NP-complete
• Recognizing shrinkable complexes is NP-complete
• The parameterized complexity of finding a 2-sphere in a simplicial complex
• Parametrized complexity of expansion height
• Shellability is NP-complete
• The parameterized complexity of finding a 2-sphere in a simplicial complex
• d-collapsibility is NP-complete for d 4
• Vertex decompositions of two-dimensional complexes and graphs
• Recognition of collapsible complexes is NP-complete
• NP-Hardness of Computing PL Geometric Category in Dimension 2
• Morphological hierarchies: a unifying framework with new trees
• A topological tree of shapes
• Parameterized inapproximability of Morse matching
• Complete, compact and topological trees of shapes

This page was built for publication: Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete

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