×

A computationally intractable problem on simplicial complexes. (English) Zbl 0849.68123

Summary: We analyze the problem of computing the minimum number of \(({\mathcal C})\) of internal simplexes that need to be removed from a simplicial 2-complex \(\mathcal 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 NP-complete even when \(\mathcal C\) is embeddable in three-dimensional space. Since the Betti numbers of \(\mathcal C\) can be computed in polynomial time, this implies that there is no polynomial time computable formula for \(\text{er}({\mathcal C})\) in terms of the Betti numbers of the complex, unless \(\text{P}= \text{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.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arora, S.; Lund, C.; Motwani, R.; Sudan, M.; Szegedy, M., Proof verification and intractability of approximation problems, (Proc. 31st Symposium on Foundations of Computer Science (1992))
[2] Bellare, M.; Goldwasser, S.; Lund, C.; Russell, A., Efficient probabilistically checkable proofs and applications to approximation, (Proc. 25th Annual Symposium on the Theory of Computing (1993)), 294-304 · Zbl 1310.68083
[3] Borowsky, E.; Gafni, E., Generalized FLP impossibility result for \(t\)-resilient asynchronous computations, (Proc. 25th Annual Symposium on the Theory of Computing (1993)), 91-100 · Zbl 1310.68078
[4] Björner, A.; Lovász, L., Linear decision trees, subspace arrangements and Möbius functions (1992), Preprint
[5] Björner, A.; Lovász, L.; Yao, A. C., Linear decision trees: volume estimates and topological bounds, (Proc. 24th Annual Symposium on the Theory of Computing (1992)), 170-177
[6] Cook, S. A., The complexity of theorem proving procedures, (Proc. 3rd Annual Symposium on the Theory of Computing. Proc. 3rd Annual Symposium on the Theory of Computing, Association for Computing Machinery, New York (1971)), 151-158 · Zbl 0363.68125
[7] Eğecioğlu, Ö.; Gonzalez, T. F., A computationally intractable problem on simplicial complexes, Tech. Rep. UCSB TRCS93-1 (January 1993)
[8] Garey, M. J.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Company: W.H. Freeman and Company New York · Zbl 0411.68039
[9] Glaser, L. C., (Geometrical Combinatorial Topology, Vol. I (1970), Van Nostrand Reinhold Company: Van Nostrand Reinhold Company New York)
[10] Gonzalez, T. F., LP-free approximation algorithm for the minimum weight vertex cover problem, Information Processing Letters, 54, 129-131 (1995) · Zbl 0875.68531
[11] Grigoriev, D.; Karpinski, M.; Vorobjov, N., Complexity lower bounds on testing membership to a polyhedron by algebraic decision trees, (Proc. 26th Annual Symposium on the Theory of Computing (1994)), 635-643 · Zbl 1345.68158
[12] Herlihy, M.; Shavit, N., The asynchronous computability theorem for \(t\)-resilient tasks, (Proc. 25th Annual Symposium on the Theory of Computing (1993)), 111-120 · Zbl 1310.68079
[13] Hocking, J. G.; Young, G. S., Topology (1961), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0135.22701
[14] Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum), 85-103 · Zbl 0366.68041
[15] Lefschetz, S., Introduction to Topology (1949), Princeton University Press: Princeton University Press New Jersey · Zbl 0041.51801
[16] Lund, C.; Yannakakis, M., On the hardness of approximating minimization problems, (Proc. 25th Annual Symposium on the Theory of Computing (1993)), 286-293 · Zbl 1310.68094
[17] Massey, W. S., Algebraic Topology: An Introduction (1967), Harcourt-Brace: Harcourt-Brace New York · Zbl 0153.24901
[18] Munkres, J. R., Elements of Algebraic Topology (1984), Addison-Wesley: Addison-Wesley Menlo Park · Zbl 0673.55001
[19] Saks, M.; Zaharoglou, F., Wait-free \(k\)-set agreement is impossible: the topology of public knowledge, (Proc. 25th Annual Symposium on the Theory of Computing (1993)), 101-110 · Zbl 1310.68041
[20] Yao, A. C., Algebraic decision trees and Euler characteristics, (Proc. 33rd Symposium on Foundations of Computer Science (1992)), 268-277 · Zbl 0977.68556
[21] Yao, A. C., Decision tree complexity and Betti numbers, (Proc. 26th Annual Symposium on the Theory of Computing (1994)), 615-624 · Zbl 1345.68297
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.