文章基本信息

标题：Minimum Bounded Chains and Minimum Homologous Chains in Embedded Simplicial Complexes
本地全文：下载
作者：Glencora Borradaile ; William Maxwell ; Amir Nayyeri 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：164
页码：21:1-21:15
DOI：10.4230/LIPIcs.SoCG.2020.21
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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(â^S{log Î²_d})-approximation algorithm for the minimum bounded chain problem where Î²_d is the dth Betti number of ð'¦. Finally, we provide an O(â^S{log n_{d+1}})-approximation algorithm for the minimum homologous chain problem where n_{d+1} is the number of (d+1)-simplices in â"³.
关键词：computational topology; algorithmic complexity; simplicial complexes