{"ID":5438748,"CreatedAt":"2026-07-01T01:17:58.482524686Z","UpdatedAt":"2026-07-03T08:54:25.326461322Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.31369","arxiv_id":"2606.31369","title":"Constant-factor approximation of maximum distance-2 independent set in graphs of bounded merge-width","abstract":"We give a constant-factor approximation algorithm for Max Dist-2 Independent Set in graphs of bounded radius-2 merge-width. The same result holds for Min Dominating Set from [Bonamy and Geniet, 2025], [Chan et al., SODA '12]. Both approximation algorithms are LP-based, showing that the domination-to-2-independence ratio is bounded in graphs of bounded radius-2 merge-width. Moreover, this result is tight in the sense that the ratio can be unbounded in graphs of bounded radius-1 merge-width.","short_abstract":"We give a constant-factor approximation algorithm for Max Dist-2 Independent Set in graphs of bounded radius-2 merge-width. The same result holds for Min Dominating Set from [Bonamy and Geniet, 2025], [Chan et al., SODA '12]. Both approximation algorithms are LP-based, showing that the domination-to-2-independence rati...","url_abs":"https://arxiv.org/abs/2606.31369","url_pdf":"https://arxiv.org/pdf/2606.31369v1","authors":"[\"Maël Dumas\"]","published":"2026-06-30T09:02:21Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\"]","methods":"[]","has_code":false}