Hardness results for homology localization. (English) Zbl 1218.68084
Summary: We address the problem of localizing homology classes, namely, finding the cycle representing a given class with the most concise geometric measure. We study the problem with different measures: volume, diameter and radius.
For volume, that is, the 1-norm of a cycle, two main results are presented. First, we prove that the problem is NP-hard to approximate within any constant factor. Second, we prove that for homology of dimension two or higher, the problem is NP-hard to approximate even when the Betti number is \(O(1)\). The latter result leads to the inapproximability of the problem of computing the nonbounding cycle with the smallest volume and computing cycles representing a homology basis with the minimal total volume.
As for the other two measures defined by pairwise geodesic distance, diameter and radius, we show that the localization problem is NP-hard for diameter but is polynomial for radius.
Our work is restricted to homology over the \(\mathbb Z_{2}\) field. Results over other fields have been studied recently by T. K. Dey, A. N. Hirani and B. Krishnamoorthy [“Optimal homologous cycles, total unimodularity, and linear programming”, in: Proceedings of the 42nd ACM symposium on theory of computing (STOC). New York, NY: Association for Computing Machinery (ACM). 221–230 (2010)].
For volume, that is, the 1-norm of a cycle, two main results are presented. First, we prove that the problem is NP-hard to approximate within any constant factor. Second, we prove that for homology of dimension two or higher, the problem is NP-hard to approximate even when the Betti number is \(O(1)\). The latter result leads to the inapproximability of the problem of computing the nonbounding cycle with the smallest volume and computing cycles representing a homology basis with the minimal total volume.
As for the other two measures defined by pairwise geodesic distance, diameter and radius, we show that the localization problem is NP-hard for diameter but is polynomial for radius.
Our work is restricted to homology over the \(\mathbb Z_{2}\) field. Results over other fields have been studied recently by T. K. Dey, A. N. Hirani and B. Krishnamoorthy [“Optimal homologous cycles, total unimodularity, and linear programming”, in: Proceedings of the 42nd ACM symposium on theory of computing (STOC). New York, NY: Association for Computing Machinery (ACM). 221–230 (2010)].
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 55N99 | Homology and cohomology theories in algebraic topology |
| 57R95 | Realizing cycles by submanifolds |
References:
| [1] | Arkin, E.M., Hassin, R.: Minimum-diameter covering problems. Networks 36(3), 147-155 (2000) · Zbl 0973.05075 · doi:10.1002/1097-0037(200010)36:3<147::AID-NET1>3.0.CO;2-M |
| [2] | Arora, S., Babai, L., Stern, J., Sweedyk, Z.: The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Comput. Syst. Sci. 54(2), 317-331 (1997) · Zbl 0877.68067 · doi:10.1006/jcss.1997.1472 |
| [3] | Ausiello, G., Paschos, V.T.: Reductions, completeness and the hardness of approximability. Eur. J. Oper. Res. 172(3), 719-739 (2006) · Zbl 1111.90092 · doi:10.1016/j.ejor.2005.06.006 |
| [4] | Carlsson, E., Carlsson, G., de Silva, V.: An algebraic topological method for feature identification. Int. J. Comput. Geom. Appl. 16(4), 291-314 (2006) · Zbl 1098.65024 · doi:10.1142/S021819590600204X |
| [5] | Carlsson, G.: Topology and data. Bull. Am. Math. Soc. 46(2), 255-308 (2009) · Zbl 1172.62002 · doi:10.1090/S0273-0979-09-01249-X |
| [6] | Chambers, E. W.; Erickson, J.; Nayyeri, A., Homology flows, cohomology cuts (2009) · Zbl 1304.05065 |
| [7] | Chambers, E. W.; Erickson, J.; Nayyeri, A., Minimum cuts and shortest homologous cycles (2009) · Zbl 1388.05177 |
| [8] | Chen, C., Freedman, D.: Quantifying homology classes II: Localization and stability. CoRR, abs/0709.2512 (2007) |
| [9] | Chen, C.; Freedman, D., Quantifying homology classes, 169-180 (2008) · Zbl 1259.68088 |
| [10] | Chen, C., Freedman, D.: Measuring and computing natural generators for homology groups. Comput. Geom. 43(2), 169-181 (2010) · Zbl 1203.65041 · doi:10.1016/j.comgeo.2009.06.004 |
| [11] | Cohen-Steiner, D.; Edelsbrunner, H.; Morozov, D., Vines and vineyards by updating persistence in linear time, 119-126 (2006) · Zbl 1153.68388 |
| [12] | de Silva, V., Ghrist, R.: Coverage in sensor networks via persistent homology. Algebr. Geom. Topol. 7, 339-358 (2007) · Zbl 1134.55003 · doi:10.2140/agt.2007.7.339 |
| [13] | Dey, T. K.; Hirani, A. N.; Krishnamoorthy, B., Optimal homologous cycles, total unimodularity, and linear programming, 221-230 (2010) · Zbl 1293.55013 |
| [14] | Dey, T. K.; Li, K.; Sun, J., On computing handle and tunnel loops (2007) |
| [15] | Dey, T.K., Li, K., Sun, J., Cohen-Steiner, D.: Computing geometry-aware handle and tunnel loops in 3D models. ACM Trans. Graph. 27(3) (2008) |
| [16] | Dey, T. K.; Sun, J.; Wang, Y., Approximating loops in a shortest homology basis from point data, 166-175 (2010) · Zbl 1284.68592 |
| [17] | Erickson, J., Har-Peled, S.: Optimally cutting a surface into a disk. Discrete Comput. Geom. 31(1), 37-59 (2004) · Zbl 1060.68129 |
| [18] | Erickson, J.; Nayyeri, A., Minimum cuts and shortest non-separating cycles via homology covers (2011) · Zbl 1376.05146 |
| [19] | Erickson, J.; Whittlesey, K., Greedy optimal homotopy and homology generators, 1038-1046 (2005) · Zbl 1297.68239 |
| [20] | Fang, Q.; Gao, J.; Guibas, L., Locating and bypassing routing holes in sensor networks, No. 11, 187-200 (2006) |
| [21] | Guskov, I.; Wood, Z. J., Topological noise removal, 19-26 (2001) |
| [22] | Kirsanov, D., Gortler, S.J.: A discrete global minimization algorithm for continuous variational problems. Technical Report TR-14-04, Harvard University (2004) |
| [23] | MacKay, D.J.C.: Information Theory, Inference & Learning Algorithms. Cambridge University Press, Cambridge (2002) |
| [24] | Munkres, J.R.: Elements of Algebraic Topology. Addison-Wesley, Redwood (1984) · Zbl 0673.55001 |
| [25] | Niyogi, P., Smale, S., Weinberger, S.: Finding the homology of submanifolds with high confidence from random samples. Discrete Comput. Geom. 39(1), 419-441 (2008) · Zbl 1148.68048 · doi:10.1007/s00454-008-9053-2 |
| [26] | Sarkar, R.; Yin, X.; Gao, J.; Luo, F.; Gu, X. D., Greedy routing with guaranteed delivery using Ricci flows, 121-132 (2009) |
| [27] | Wikipedia. Book embedding. http://en.wikipedia.org/wiki/Book_embedding |
| [28] | Wikipedia. Suspension. http://en.wikipedia.org/wiki/Suspension_(topology) |
| [29] | Wood, Z.J., Hoppe, H., Desbrun, M., Schröder, P.: Removing excess topology from isosurfaces. ACM Trans. Graph. 23(2), 190-208 (2004) · doi:10.1145/990002.990007 |
| [30] | Zomorodian, A.; Carlsson, G., Localized homology, 189-198 (2007) · doi:10.1109/SMI.2007.25 |
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.
