Volume 2010

Article 3

Published by the Department of Computer Science, The University of Chicago.

$d$-collapsibility is NP-complete for $d \ge 4$

Martin Tancer
Department of Applied Mathematics and Institute for Theoretical Computer Science
Faculty of Mathematics and Physics, Charles University
Malostranské ná 25, 118 00 Prague, Czech Republic

June 21, 2010
Abstract

A simplicial complex is d-collapsible if it can be reduced to an empty complex by repeatedly removing (collapsing) a face of dimension at most $d-1$ that is contained in a unique maximal face. We prove that the algorithmic question whether a given simplicial complex is $d$-collapsible is NP-complete for $d \ge 4$ and polynomial time solvable for $d\le 2$.

As an intermediate step, we prove that d-collapsibility can be recognized by the greedy algorithm for $d \le 2$, but the greedy algorithm does not work for $d \ge3$.

A simplicial complex is d-representable if it is the nerve of a collection of convex sets in ${\mathbb R}^d$. The main motivation for studying $d$-collapsible complexes is that every $d$-representable complex is $d$-collapsible. We also observe that known results imply that $d$-representability is NP-hard to decide for $d \ge 2$.

• The article: PDF (721,885 bytes)
• Source materials: ZIP (464,894 bytes)
• Self citation in BIBTeX (205 bytes)
• Original version (pre-June 2010): PDF (320,560 bytes)

Submitted October 23, 2008, revised June 15, 2010, published June 21, 2010.

Volume 2010, Article 2
Volume 2009 Published articles

This document last modified on: 06/03/2011 22:02:54