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.05208MaRDI 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 complex; NP-complete; d-collapsibility; d-representability

Mathematics Subject Classification ID

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

05C85: Graph algorithms (graph-theoretic aspects)

05E45: Combinatorial aspects of simplicial complexes

Related Items

Complexes of graphs with bounded independence number

Cites Work

• Unnamed Item
• Unnamed Item
• 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