d-collapsibility is NP-complete for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:mi>d</mml:mi><mml:mo>⩾</mml:mo><mml:mn>4</mml:mn></mml:math>

DOI10.1016/j.endm.2009.07.009zbMath1272.05208OpenAlexW1483148630MaRDI QIDQ2851437

Martin Tancer

Publication date: 10 October 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2009.07.009

zbMATH Keywords

simplicial complexNP-completed-collapsibilityd-representability

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial aspects of simplicial complexes (05E45)

Related Items

Oriented matroids and combinatorial neural codes ⋮ Unnamed Item ⋮ Complexes of graphs with bounded independence number

Cites Work

• String graphs. II: Recognizing string graphs is NP-hard
• d-collapsing and nerves of families of convex sets
• Representation of a finite graph by a set of intervals on the real line
• Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete
• 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
• Unnamed Item
• Unnamed Item