摘要
我们提出了一种常数因子近似算法，用于解决在有界半径-2合并宽度图中的最大距离-2独立集问题。此结果同样适用于最小支配集问题，参考文献包括 [Bonamy and Geniet, 2025] 和 [Chan et al., SODA '12]。这两种近似算法均基于线性规划，表明在有界半径-2合并宽度图中，支配到2-独立集的比率是有界的。此外，该结果是紧的，因为在有界半径-1合并宽度图中，该比率可以是无界的。
博主点评： 该研究展示了在特定图结构下的有效近似算法，尤其是在合并宽度的限制下，提供了新的思路来处理独立集和支配集问题。这为图论和近似算法的研究提供了重要的理论基础，尤其是在算法复杂性方面的深入理解。