论文标题
嵌入式简单复合物中的最小界链和最小同源链
Minimum bounded chains and minimum homologous chains in embedded simplicial complexes
论文作者
论文摘要
我们研究了与$ \ Mathbb {z} _2 $的同源性的简单复合物上的两个优化问题，最小界链问题：给定$ d $ - 二维复杂$ \ Mathcal {k} $嵌入在$ \ Mathbb {r} $ \ MATHCAL {K} $，找到带边界$ c $的最低$ D $ - 链，以及最小同源链问题：给定$（d+1）$ - 歧管$ \ Mathcal {M Mathcal {M} $和A $ D $ - Chain $ - Chain $ d $ in Mathcal {m} $ in Mathcal {m} $，找到$ d $ d $ $ d $ $ d $ d $。即使对于$ d $的少量值，我们也会为这两个问题显示出强烈的硬度结果； $ d = 2 $用于以前的问题，而后一个问题的$ d = 1 $。我们表明，这两个问题都是APX，并且在任何常数因素内都难以近似，假设唯一的游戏猜想。在正面，我们证明两个问题都是相对于最佳解决方案的尺寸固定参数。此外，我们提供了一个$ o（\ sqrt {\logβ_d}）$ - 对于最小界链问题的近似算法，其中$β_D$是$ d $ t $ t $ th betti $ \ mathcal {k} $。最后，我们提供了一个$ o（\ sqrt {\ log n_ {d+1}}）$ - 最小同源链问题的近似算法，其中$ n_ {d+1} $是$ d $ -simplices in $ \ m nathcal {m} $的$ d $ simplices的数量。
We study two optimization problems on simplicial complexes with homology over $\mathbb{Z}_2$, the minimum bounded chain problem: given a $d$-dimensional complex $\mathcal{K}$ embedded in $\mathbb{R}^{d+1}$ and a null-homologous $(d-1)$-cycle $C$ in $\mathcal{K}$, find the minimum $d$-chain with boundary $C$, and the minimum homologous chain problem: given a $(d+1)$-manifold $\mathcal{M}$ and a $d$-chain $D$ in $\mathcal{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(\sqrt{\log β_d})$-approximation algorithm for the minimum bounded chain problem where $β_d$ is the $d$th Betti number of $\mathcal{K}$. Finally, we provide an $O(\sqrt{\log n_{d+1}})$-approximation algorithm for the minimum homologous chain problem where $n_{d+1}$ is the number of $d$-simplices in $\mathcal{M}$.
