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

NP-completenessComputational ComplexityCollapsingSimplicial Topology

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 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 \geq 4\)
• \(D\)-collapsibility is NP-complete for \(d \geq 4\)
• Embeddability of Simplicial Complexes is Undecidable

Cites work

• 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?)
• A computationally intractable problem on simplicial complexes
• A concise characterization of 3D simple points
• The complexity of theorem-proving procedures

Cited in

(18)

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

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)