{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,24]],"date-time":"2025-06-24T04:03:16Z","timestamp":1750737796882,"version":"3.41.0"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T00:00:00Z","timestamp":1748476800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T00:00:00Z","timestamp":1748476800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005416","name":"Norges Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["274526"],"award-info":[{"award-number":["274526"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100016999","name":"Western Norway University Of Applied Sciences","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100016999","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Appl. and Comput. Topology"],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Homology localization means finding a cycle of lowest weight that represents a homology class in a simplicial complex. It is an NP-complete problem, which this paper addresses using parameterized complexity theory. We prove that to find even a constant factor approximation to this problem is W[1]-hard when solution size is used as a parameter. We have also designed and implemented two new algorithms that are fixed parameter tractable when parameterized by the treewidth of graphs associated to the simplicial complex. The running time of both algorithms matches the lower bounds we obtain from the exponential time hypothesis. We analysed the performance of the two algorithms experimentally and found that one algorithm is significantly faster than the other.<\/jats:p>","DOI":"10.1007\/s41468-025-00212-0","type":"journal-article","created":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T15:30:44Z","timestamp":1748532644000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Homology localization through the looking-glass of\u00a0parameterized complexity theory"],"prefix":"10.1007","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9489-1657","authenticated-orcid":false,"given":"Nello","family":"Blaser","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2289-2268","authenticated-orcid":false,"given":"Erlend Raa","family":"V\u00e5gset","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,29]]},"reference":[{"unstructured":"Bhattacharyya, A., Bonnet, \u00c9., Egri, L., Ghoshal, S., Lin, B., Manurangsi, P., Marx, D., et\u00a0al.: Parameterized intractability of even set and shortest vector problem. arXiv preprint arXiv: 1909.01986, (2019)","key":"212_CR1"},{"issue":"6","key":"212_CR2","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"Hans L Bodlaender","year":"1996","unstructured":"Bodlaender, Hans L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"212_CR3","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/130947374","volume":"45","author":"HL Bodlaender","year":"2016","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: A $$c^{k} n$$ 5-approximation algorithm for treewidth. SIAM J. Comput. 45(2), 317\u2013378 (2016)","journal-title":"SIAM J. Comput."},{"unstructured":"Borradaile, G., Maxwell, W., Nayyeri, A.: Minimum bounded chains and minimum homologous chains in embedded simplicial complexes. arXiv preprint arXiv:2003.02801, (2020)","key":"212_CR4"},{"key":"212_CR5","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/978-3-642-31155-0_17","volume-title":"Algorithm Theory \u2013 SWAT 2012","author":"O Busaryev","year":"2012","unstructured":"Busaryev, O., Cabello, S., Chen, C., Dey, T.K., Wang, Y.: Annotating simplices with a homology basis and its applications. In: Fomin, Fedor V., Kaski, Petteri (eds.) Algorithm Theory \u2013 SWAT 2012, pp. 189\u2013200. Springer, Heidelberg (2012)"},{"issue":"2","key":"212_CR6","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1090\/S0273-0979-09-01249-X","volume":"46","author":"G Carlsson","year":"2009","unstructured":"Carlsson, G.: Topology and data. Bull. Amer. Math. Soc. (N.S.) 46(2), 255\u2013308 (2009)","journal-title":"Bull. Amer. Math. Soc. (N.S.)"},{"doi-asserted-by":"crossref","unstructured":"Chambers, E.W., Erickson, J., Nayyeri, A.: Minimum cuts and shortest homologous cycles. In Proceedings of the twenty-fifth annual symposium on Computational geometry, pages 377\u2013385, (2009)","key":"212_CR7","DOI":"10.1145\/1542362.1542426"},{"issue":"3","key":"212_CR8","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/s00454-010-9322-8","volume":"45","author":"C Chen","year":"2011","unstructured":"Chen, C., Freedman, D.: Hardness results for homology localization. Discrete & Computational Geometry 45(3), 425\u2013448 (2011)","journal-title":"Discrete & Computational Geometry"},{"doi-asserted-by":"publisher","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms (2015) Springer, ISBN 978-3-319-21274-6. https:\/\/doi.org\/10.1007\/978-3-319-21275-3","key":"212_CR9","DOI":"10.1007\/978-3-319-21275-3"},{"doi-asserted-by":"publisher","unstructured":"Dell, H., Komusiewicz, C., Talmon, N., Weller, M.: The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The Second Iteration. In Daniel Lokshtanov and Naomi Nishimura, editors, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), volume\u00a089 of Leibniz International Proceedings in Informatics (LIPIcs), pages 30:1\u201330:12, Dagstuhl, Germany, 2018. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-051-4. https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2017.30. URL http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/8558","key":"212_CR10","DOI":"10.4230\/LIPIcs.IPEC.2017.30"},{"key":"212_CR11","volume-title":"Parameterized Complexity","author":"RG Downey","year":"2012","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (2012)"},{"doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R., Stege, U.: Parameterized complexity: A framework for systematically confronting computational intractability. In Contemporary trends in discrete mathematics: From DIMACS and DIMATIA to the future 49, 49\u201399 (1999)","key":"212_CR12","DOI":"10.1090\/dimacs\/049\/04"},{"doi-asserted-by":"publisher","unstructured":"Funke, S.: Topological hole detection in wireless sensor networks and its applications. In Proceedings of the 2005 Joint Workshop on Foundations of Mobile Computing, DIALM-POMC \u201905, page 44-53, New York, NY, USA, 2005. Association for Computing Machinery. ISBN 1595930922. https:\/\/doi.org\/10.1145\/1080810.1080819","key":"212_CR13","DOI":"10.1145\/1080810.1080819"},{"doi-asserted-by":"crossref","unstructured":"Guskov, I., Wood, Z.J.: Topological noise removal. In Proceedings of Graphics Interface 2001, GI \u201901, page 19-26, CAN, (2001). Canadian Information Processing Society. ISBN 0968880800","key":"212_CR14","DOI":"10.1142\/S0219467801000037"},{"unstructured":"Guss, W.H., Salakhutdinov, R.: On characterizing the capacity of neural networks using algebraic topology, (2018)","key":"212_CR15"},{"doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs of bounded treewidth are probably optimal. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 777\u2013789. SIAM, (2011)","key":"212_CR16","DOI":"10.1137\/1.9781611973082.61"},{"doi-asserted-by":"publisher","unstructured":"Rabadan, R., Blumberg, A.J.: Topological Data Analysis for Genomics and Evolution: Topology in Biology. Cambridge University Press (2019). https:\/\/doi.org\/10.1017\/9781316671665","key":"212_CR17","DOI":"10.1017\/9781316671665"},{"doi-asserted-by":"publisher","unstructured":"Venkataraman, V., Ramamurthy, K.N., Turaga P.: Persistent homology of attractors for action recognition. In 2016 IEEE International Conference on Image Processing, ICIP 2016 - Proceedings, volume 2016-August, pages 4150\u20134154, United States, 8 2016. IEEE Computer Society. https:\/\/doi.org\/10.1109\/ICIP.2016.7533141. 23rd IEEE International Conference on Image Processing, ICIP 2016 ; Conference date: 25-09-2016 Through 28-09-2016","key":"212_CR18","DOI":"10.1109\/ICIP.2016.7533141"},{"doi-asserted-by":"crossref","unstructured":"Wu, P., Chen, C., Wang, Y., Zhang, S., Yuan, C., Qian, Z., Etaxas, D., Axel, L.: Optimal topological cycles and their application in cardiac trabeculae restoration. In International Conference on Information Processing in Medical Imaging, pages 80\u201392. Springer, (2017)","key":"212_CR19","DOI":"10.1007\/978-3-319-59050-9_7"},{"doi-asserted-by":"crossref","unstructured":"Zhang, X., Wu, P., Yuan, C., Wang, Y., Metaxas, D.N., Chen, C.: Heuristic search for homology localization problem and its application in cardiac trabeculae reconstruction. In IJCAI, pages 1312\u20131318, (2019)","key":"212_CR20","DOI":"10.24963\/ijcai.2019\/182"}],"container-title":["Journal of Applied and Computational Topology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41468-025-00212-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41468-025-00212-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41468-025-00212-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T12:25:37Z","timestamp":1750681537000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41468-025-00212-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,29]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["212"],"URL":"https:\/\/doi.org\/10.1007\/s41468-025-00212-0","relation":{},"ISSN":["2367-1726","2367-1734"],"issn-type":[{"type":"print","value":"2367-1726"},{"type":"electronic","value":"2367-1734"}],"subject":[],"published":{"date-parts":[[2025,5,29]]},"assertion":[{"value":"25 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 January 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 April 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 May 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflicts of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of Interest\/Competing interests"}}],"article-number":"16"}}