用于重构问题的间隙放大技术

《ACM Transactions on Algorithms》：Gap Amplification for Reconfiguration Problems

组合重配置问题的近似困难性研究，通过改进gap放大技术，在Reconfiguration Inapproximability Hypothesis下证明了Maxmin 2-CSP重配置因子0.9942难近似，并应用到集合覆盖与支配集重配置问题，分别难近似于1.0029和1.00?0.0058因子。

　　

摘要

组合重构是一个全新的研究领域，旨在探讨组合问题解空间的连通性。我们研究了实现“近似”重构性的难度，这种重构性允许放宽中间解的可行性。例如，在最小最大集合覆盖重构问题中，给定一个集合族及其两个覆盖方案，我们需要通过反复从该集合族中添加或移除一个集合，将一个覆盖方案转换为另一个覆盖方案。目标是在转换过程中最小化遇到的覆盖方案的最大大小。Ohsaka（STACS 2023）的最新研究表明，假设重构不可近似性假设（RIH）成立，多个重构问题是PSPACE难近似的。这种方法的一个局限性在于没有明确显示不可近似性因子，因此即使对于$1.00?001$的近似算法，也不能排除其可行性；而根据Ito、Demaine、Harvey、Papadimitriou、Sideri、Uehara和Uno（TCS 2011）的研究，该问题存在一个$2$因子近似算法。

在本文中，我们展示了重构问题的间隙放大现象。具体来说，我们在仅假设RIH的情况下，证明了三个重构问题的近似因子具有明确的PSPACE难度。我们的主要结果是，在RIH条件下，最大最小2-CSP重构问题在$0.9942$的因子范围内是PSPACE难近似的。其证明的核心是对Dinur（JACM 2007）提出的间隙放大技术的改进，该方法将原本的$1$与$1?\epsilon$之间的间隙扩大到了$1$与$1?0.0058$之间的间隙。作为主要结果的一个应用，我们进一步证明了在RIH条件下，最小最大集合覆盖重构和最小最大支配集重构问题在$1.0029$的因子范围内也是PSPACE难近似的。