License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.21
URN: urn:nbn:de:0030-drops-121799
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12179/
Go to the corresponding LIPIcs Volume Portal

Borradaile, Glencora ; Maxwell, William ; Nayyeri, Amir

Minimum Bounded Chains and Minimum Homologous Chains in Embedded Simplicial Complexes

pdf-format:
LIPIcs-SoCG-2020-21.pdf (0.5 MB)

Abstract

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 ℳ.

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:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Sergio Cabello and Danny Z. Chen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12179},
  URN =		{urn:nbn:de:0030-drops-121799},
  doi =		{10.4230/LIPIcs.SoCG.2020.21},
  annote =	{Keywords: computational topology, algorithmic complexity, simplicial complexes}
}

Keywords: computational topology, algorithmic complexity, simplicial complexes
Collection: 36th International Symposium on Computational Geometry (SoCG 2020)
Issue Date: 2020
Date of publication: 08.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI