Borradaile, Glencora ;
Maxwell, William ;
Nayyeri, Amir
Minimum Bounded Chains and Minimum Homologous Chains in Embedded Simplicial Complexes
Abstract
We study two optimization problems on simplicial complexes with homology over ℤ₂, the minimum bounded chain problem: given a ddimensional complex 𝒦 embedded in ℝ^(d+1) and a nullhomologous (d1)cycle C in 𝒦, find the minimum dchain with boundary C, and the minimum homologous chain problem: given a (d+1)manifold ℳ and a dchain D in ℳ, find the minimum dchain 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 APXhard, and hard to approximate within any constant factor assuming the unique games conjecture. On the positive side, we show that both problems are fixedparameter 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 ℳ.
BibTeX  Entry
@InProceedings{borradaile_et_al:LIPIcs:2020:12179,
author = {Glencora Borradaile and William Maxwell and Amir Nayyeri},
title = {{Minimum Bounded Chains and Minimum Homologous Chains in Embedded Simplicial Complexes}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {21:121:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771436},
ISSN = {18688969},
year = {2020},
volume = {164},
editor = {Sergio Cabello and Danny Z. Chen},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12179},
URN = {urn:nbn:de:0030drops121799},
doi = {10.4230/LIPIcs.SoCG.2020.21},
annote = {Keywords: computational topology, algorithmic complexity, simplicial complexes}
}
08.06.2020
Keywords: 

computational topology, algorithmic complexity, simplicial complexes 
Seminar: 

36th International Symposium on Computational Geometry (SoCG 2020)

Issue date: 

2020 
Date of publication: 

08.06.2020 