Recognition of collapsible complexes is NP-complete
From MaRDI portal
Simplicial sets and complexes in algebraic topology (55U10) 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)
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
- d-collapsibility is NP-complete for d 4
- A computationally intractable problem on simplicial complexes
- Computing Optimal Morse Matchings
- d-collapsing and nerves of families of convex sets
- 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
- 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?)
- 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
Cited in
(36)- Collapsibility to a subcomplex of a given dimension is NP-complete
- On distance-preserving elimination orderings in graphs: complexity and algorithms
- A computationally intractable problem on simplicial complexes
- Recognising a partitionable simplicial complex is in \(\text{NP}\)
- Shellings from relative shellings, with an application to NP-completeness
- The worst way to collapse a simplex
- Unlabeled sample compression schemes and corner peelings for ample and maximum classes
- Inverting the discrete curl operator: a novel graph algorithm to find a vector potential of a given vector field
- Extremal examples of collapsible complexes and random discrete Morse theory
- A note on independence complexes of chordal graphs and dismantling
- D-collapsibility is NP-complete for d 4
- Recognizing shrinkable complexes is NP-complete
- Recognizing shrinkable complexes is NP-complete
- Neural codes, decidability, and a new local obstruction to convexity
- Parametrized complexity of expansion height
- Computing persistent homology of flag complexes via strong collapses
- Shellability is NP-complete
- The trisection genus of standard simply connected PL 4-manifolds
- Shellability is NP-complete
- d-collapsibility is NP-complete for d 4
- Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete
- Vertex decompositions of two-dimensional complexes and graphs
- What makes a neural code convex?
- Determining the Trisection Genus of Orientable and Non-Orientable PL 4-Manifolds through Triangulations
- Recognition of collapsible complexes is NP-complete
- Generalised cone complexes and tropical moduli in polymake
- New directions in real algebraic geometry. Abstracts from the workshop held March 19--24, 2023
- NP-Hardness of Computing PL Geometric Category in Dimension 2
- Completions and ramifications
- Shellable tilings on relative simplicial complexes and their h-vectors
- Cholesky-like preconditioner for Hodge Laplacians via heavy collapsible subcomplex
- A counterexample to Wegner's conjecture on good covers
- Random simple-homotopy theory
- Complexity of simplicial homology and independence complexes of chordal graphs
- Parameterized inapproximability of Morse matching
- Enumeration of interval graphs and d-representable complexes
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)
