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

DOI10.1007/978-3-540-79126-3_17zbMATH Open1138.68604OpenAlexW1556856743MaRDI QIDQ5458885FDOQ5458885

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of theorem-proving procedures
• Title not available (Why is that?)
• A concise characterization of 3D simple points
• A computationally intractable problem on simplicial complexes
• Title not available (Why is that?)

Cited In (19)

• Shellability is NP-complete
• Vertex decompositions of two-dimensional complexes and graphs
• The parameterized complexity of finding a 2-sphere in a simplicial complex
• Parameterized complexity of discrete Morse theory
• 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
• The parameterized complexity of finding a 2-sphere in a simplicial complex
• Shellings from relative shellings, with an application to NP-completeness
• 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
• Recognition of collapsible complexes is NP-complete
• \(d\)-collapsibility is NP-complete for \(d \geq 4\)
• Frontiers of sphere recognition in practice

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)