Recognition of collapsible complexes is NP-complete
From MaRDI portal
Publication:5964219
DOI10.1007/s00454-015-9747-1zbMath1335.68286arXiv1211.6254MaRDI QIDQ5964219
Publication date: 29 February 2016
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1211.6254
68Q25: Analysis of algorithms and problem complexity
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
55U10: Simplicial sets and complexes in algebraic topology
Related Items
Neural Codes, Decidability, and a New Local Obstruction to Convexity, Unnamed Item, Unnamed Item, Unnamed Item, Computing Persistent Homology of Flag Complexes via Strong Collapses, What Makes a Neural Code Convex?, Recognition of collapsible complexes is NP-complete, Determining the Trisection Genus of Orientable and Non-Orientable PL 4-Manifolds through Triangulations, 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, Complexity of simplicial homology and independence complexes of chordal graphs, Collapsibility to a subcomplex of a given dimension is NP-complete, On distance-preserving elimination orderings in graphs: complexity and algorithms, 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
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Geometry-driven collapses for converting a Čech complex into a triangulation of a nicely triangulable shape
- d-collapsing and nerves of families of convex sets
- Morse theory for cell complexes
- Einstein structures: Existence versus uniqueness
- A computationally intractable problem on simplicial complexes
- Discrete Morse theory for manifolds with boundary
- THE PROBLEM OF DISCRIMINATING ALGORITHMICALLY THE STANDARD THREE-DIMENSIONAL SPHERE
- d-collapsibility is NP-complete for d greater or equal to 4
- Random Discrete Morse Theory and a New Library of Triangulations
- Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete
- Computing Optimal Morse Matchings
- 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
- Recognition of collapsible complexes is NP-complete
