A Computationally Intractable Problem on Simplicial Complexes

We analyze the problem of computing the minimum number er(C) of internalsimplexes that need to be removed from a simplicial 2-complex C so that theremaining complex can be nulled by deleting a sequence of external simplexes.This is equivalent to requiring that the resulting complex be collapsible to a1-complex. By reducing a restricted version of SAT, we show that this problemis NP-complete and therefore computationally intractable. This implies thatthere is no simple formula for er(C) terms of the Betti numbers of thecomplex. The problem remains NP-complete for higher dimensional complexes, butcan be solved in polynomial time for graphs.