d-collapsibility is NP-complete for d greater or equal to 4

DOI10.4086/cjtcs.2010.003zbMath1286.68210arXiv0808.1991OpenAlexW4254521354MaRDI QIDQ5414577

Martin Tancer

Publication date: 6 May 2014

Published in: Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0808.1991

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Extensions of the colorful Helly theorem for d-collapsible and d-Leray complexes ⋮ Planar Convex Codes are Decidable ⋮ Tight complexes in 3-space admit perfect discrete Morse functions ⋮ A counterexample to Wegner's conjecture on good covers ⋮ Recognition of collapsible complexes is NP-complete ⋮ Chordality, \(d\)-collapsibility, and componentwise linear ideals

This page was built for publication: d-collapsibility is NP-complete for d greater or equal to 4