Computational Geometry, Theory and Applications, 6 (1996) pp. 85-98.
Ömer Egecioglu and Teofilo F. Gonzalez
A Computationally Intractable Problem on Simplicial Complexes
Abstract.
We analyze the problem of computing the minimum number $er({\cal C})$ of
internal simplexes that need to be removed from a simplicial 2-complex
${\cal C}$ so that the remaining complex can be nulled by deleting a sequence
of external simplexes. We show that the decision version of this problem is
${\cal NP}$-complete even when ${\cal C}$ is embeddable in 3-dimensional space.
Since the Betti numbers of ${\cal C}$ can be computed in polynomial time, this
implies that there is no polynomial time computable formula for $er({\cal C})$
in terms of the Betti numbers of the complex, unless ${\cal P = NP}$. The problem
can be solved in linear time for 1-complexes (graphs).
Our reduction can also be used to show that the corresponding approximation
problem is at least as difficult as the one for the minimum cardinality vertex
cover, and what is worse, as difficult as the minimum set cover problem. Thus
simple heuristics may generate solutions that are arbitrarily far from optimal.
omer@cs.ucsb.edu