Abstract
We present a constant-factor approximation algorithm for the Max Dist-2 Independent Set problem in graphs of bounded radius-2 merge-width. The same result holds for the Min Dominating Set problem, as referenced in [Bonamy and Geniet, 2025] and [Chan et al., SODA '12]. Both approximation algorithms are LP-based, indicating that the domination-to-2-independence ratio is bounded in graphs of bounded radius-2 merge-width. Furthermore, this result is tight as the ratio can be unbounded in graphs of bounded radius-1 merge-width.
Blogger's Review: This study introduces effective approximation algorithms within specific graph structures, particularly under the constraints of merge width, offering new insights into handling independent and dominating set problems. It provides a significant theoretical foundation for research in graph theory and approximation algorithms, especially regarding the understanding of algorithmic complexity.