On 06.06.2013 at 12:20 in S6, there is the following noon lecture:
Recognition of collapsible complexes is NP-complete
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.
Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010