Recognition of collapsible complexes is NP-complete
From MaRDI portal
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Simplicial sets and complexes in algebraic topology (55U10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Abstract: We prove that it is NP-complete to decide whether a given (3-dimensional) simplicial complex is collapsible. This work extends a result of Malgouyres and Franc'{e}s showing that it is NP-complete to decide whether a given simplicial complex collapses to a 1-complex.
Recommendations
Cites work
- scientific article; zbMATH DE number 4102053 (Why is no real title available?)
- scientific article; zbMATH DE number 529110 (Why is no real title available?)
- scientific article; zbMATH DE number 2103273 (Why is no real title available?)
- A computationally intractable problem on simplicial complexes
- Computing Optimal Morse Matchings
- Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete
- Discrete Morse theory for manifolds with boundary
- Einstein structures: Existence versus uniqueness
- Geometry-driven collapses for converting a Čech complex into a triangulation of a nicely triangulable shape
- Morse theory for cell complexes
- Random discrete Morse theory and a new library of triangulations
- Recognition of collapsible complexes is NP-complete
- THE PROBLEM OF DISCRIMINATING ALGORITHMICALLY THE STANDARD THREE-DIMENSIONAL SPHERE
- 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
- d-collapsibility is NP-complete for d 4
- d-collapsing and nerves of families of convex sets
Cited in
(34)- A note on independence complexes of chordal graphs and dismantling
- Neural codes, decidability, and a new local obstruction to convexity
- What makes a neural code convex?
- Shellability is NP-complete
- Shellability is NP-complete
- Vertex decompositions of two-dimensional complexes and graphs
- Unlabeled sample compression schemes and corner peelings for ample and maximum classes
- Determining the Trisection Genus of Orientable and Non-Orientable PL 4-Manifolds through Triangulations
- On distance-preserving elimination orderings in graphs: complexity and algorithms
- New directions in real algebraic geometry. Abstracts from the workshop held March 19--24, 2023
- Parametrized complexity of expansion height
- Computing persistent homology of flag complexes via strong collapses
- D-collapsibility is NP-complete for d 4
- Parameterized inapproximability of Morse matching
- Generalised cone complexes and tropical moduli in polymake
- Inverting the discrete curl operator: a novel graph algorithm to find a vector potential of a given vector field
- Cholesky-like preconditioner for Hodge Laplacians via heavy collapsible subcomplex
- NP-Hardness of Computing PL Geometric Category in Dimension 2
- The worst way to collapse a simplex
- Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete
- Extremal examples of collapsible complexes and random discrete Morse theory
- Random simple-homotopy theory
- Enumeration of interval graphs and d-representable complexes
- 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
- A counterexample to Wegner's conjecture on good covers
- The trisection genus of standard simply connected PL 4-manifolds
- Completions and ramifications
- Shellable tilings on relative simplicial complexes and their h-vectors
- Complexity of simplicial homology and independence complexes of chordal graphs
- Recognition of collapsible complexes is NP-complete
- d-collapsibility is NP-complete for d 4
This page was built for publication: Recognition of collapsible complexes is NP-complete
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5964219)
