Hardness of Approximation for Morse Matching
Hardness of Approximation for Morse Matching
复制标题
莫尔斯匹配的近似硬度
DOI：
10.1137/1.9781611975482.165
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Abhishek Rathod
中科院分区：
文献类型：
--
作者：
Ulrich Bauer;Abhishek Rathod
我们考虑的近似性的最大化和最小化的莫尔斯匹配问题的变种，Joswig和Pfetsch提出的开放问题。我们建立了最大莫尔斯匹配和最小莫尔斯匹配的硬度结果。特别是，我们表明，对于一个单纯复形与n个单形和尺寸$d \leq 3$，它是NP-难近似Min-Morse匹配的一个因素内的$O（n^{1-\displaystyle}）$，任何$\displaystyle> 0$。此外，使用的L-约化从度3最大-无环子图的最大-Morse匹配，我们表明，它是NP-难和UGC-难的近似最大-Morse匹配的维数为d \leq 2$在某些显式常数因子。
We consider the approximability of maximization and minimization variants of the Morse matching problem, posed as open problems by Joswig and Pfetsch. We establish hardness results for Max-Morse matching and Min-Morse matching. In particular, we show that, for a simplicial complex with n simplices and dimension $d \leq 3$, it is NP-hard to approximate Min-Morse matching within a factor of $O(n^{1-\epsilon})$, for any $\epsilon > 0$. Moreover, using an L-reduction from Degree 3 Max-Acyclic Subgraph to Max-Morse matching, we show that it is both NP-hard and UGC-hard to approximate Max-Morse matching for simplicial complexes of dimension $d \leq 2$ within certain explicit constant factors.