摘要
对于每个 $\varepsilon > 0$，在有效有限双宽的 $n$-顶点图中，最大独立集问题（Max Independent Set）存在一个多项式时间的 $n^\varepsilon$-近似算法 [Bergé et al., STACS '23]。实际上获得的近似因子为 $n^{O(1/ \log \log n)}$。在此之前，尚无关于该问题的近似难度的已知结果，关于多项式时间近似方案（PTAS）的存在问题被反复提出为开放问题。
我们以强有力的方式回答了这个问题：我们证明存在一个常数 $\gamma > 0$，使得在双宽至多为 4 的图上，若存在一个多项式时间的 $n^{\gamma/ (\log \log n)^2}$-近似算法，则将推翻指数时间假设（ETH）。如果输入中提供了一个 4-序列，则这一下界也适用。
我们还证明了最小着色问题（Min Coloring）的近似难度也相同，该问题在有效有限双宽的图上同样拥有接近的 $n^{O(1/ \log \log n)}$-近似算法。此外，我们进一步阐明了在半径 $r$ 合并宽度受限的图上 $k$-独立集问题的参数复杂性。
当 $r$ 的范围有限时，给定半径为 $2^{O(k^2)}$ 的合并序列的图上，$k$-独立集问题存在一个固定参数可解的算法 [Dreier and Toruńczyk, STOC '25]。我们通过证明在半径为 $o(k)$ 的合并序列下，$k$-独立集问题是 W[1]-困难的，进一步补充了这一结果。此结论同样适用于 $k$-主导集问题（k-Dominating Set）。
博主点评： 该研究揭示了在特定结构限制下图的独立集问题的近似难度，提供了新的理论证据支持指数时间假设的合理性，进一步推动了对图的参数化复杂性的理解。研究结果不仅对独立集问题，也对最小着色及其他相关问题具有重要的启示意义。