Report ID
Report Authors
Omer Egecioglu and Teofilo Gonzalez
Report Date
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.
1993-01.ps852.84 KB