2026-08-04T08:54:31Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:12179 2024-03-06T10:49:38Z ddc:004 open_access
Minimum Bounded Chains and Minimum Homologous Chains in Embedded Simplicial Complexes Borradaile, Glencora Maxwell, William Nayyeri, Amir computational topology algorithmic complexity simplicial complexes We study two optimization problems on simplicial complexes with homology over β„€β‚‚, the minimum bounded chain problem: given a d-dimensional complex 𝒦 embedded in ℝ^(d+1) and a null-homologous (d-1)-cycle C in 𝒦, find the minimum d-chain with boundary C, and the minimum homologous chain problem: given a (d+1)-manifold β„³ and a d-chain D in β„³, find the minimum d-chain homologous to D. We show strong hardness results for both problems even for small values of d; d = 2 for the former problem, and d=1 for the latter problem. We show that both problems are APX-hard, and hard to approximate within any constant factor assuming the unique games conjecture. On the positive side, we show that both problems are fixed-parameter tractable with respect to the size of the optimal solution. Moreover, we provide an O(√{log Ξ²_d})-approximation algorithm for the minimum bounded chain problem where Ξ²_d is the dth Betti number of 𝒦. Finally, we provide an O(√{log n_{d+1}})-approximation algorithm for the minimum homologous chain problem where n_{d+1} is the number of (d+1)-simplices in β„³. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Glencora Borradaile and William Maxwell and Amir Nayyeri 2020 Is Part Of LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2020.21 urn:nbn:de:0030-drops-121799 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.21 eng https://creativecommons.org/licenses/by/3.0/legalcode