#

### 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