Abstract
A Computationally Intractable Problem on Simplicial Complexes
by: Omer Egecioglu and Teofilo Gonzalez
Abstract:
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.
Keywords:
Simplicial complex, collapsing, Betti number, algorithmiccomplexity, intractable problem.
Date:
January 1993
Document: 1993-01
