Department of
Applied
Mathematics

Recognition of collapsible complexes is NP-complete

Martin Tancer

Abstract

A simplicial complex K is collapsible if there is a sequence of elementary collapses collapsing K to a point. By an elementary collapse we mean the removal of all proper superfaces of some face which is contained in exactly one maximal proper superface. Elementary collapses preserve the homotopy type; thus, collapsible complexes form an important subclass of contractible complexes--describable by a combinatorial condition.

We sketch a proof that it is NP-complete to decide whether a given (3-dimensional) simplicial complex is collapsible. This work extends a result of Malgouyres and Francés showing that it is NP-complete to decide whether a given simplicial complex collapses to a 1-complex.