# Minimum bounded chains and minimum homologous chains in embedded simplicial complexes

arXiv: https://arxiv.org/abs/2003.02801 · HTML: https://mlsanity.com/paper/2003.02801/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Mar 2020.

## Built on by (most cited first, 2 of 2)

- [Minimal Cycle Representatives in Persistent Homology using Linear Programming: an Empirical Study with User's Guide](https://mlsanity.com/paper/2105.07025/) (2021)
- [Geometric Localization of Homology Cycles](https://mlsanity.com/paper/2406.03183/) (2024)

## Abstract (arXiv)

We study two optimization problems on simplicial complexes with homology over mathbbZ2, the minimum bounded chain problem: given a d-dimensional complex K embedded in ℝd+1 and a null-homologous (d-1)-cycle C in K, find the minimum d-chain with boundary C, and the minimum homologous chain problem: given a (d+1)-manifold M and a d-chain D in M, 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 K. Finally, we provide an O(√log nd+1)-approximation algorithm for the minimum homologous chain problem where nd+1 is the number of d-simplices in M.