MIS vs. Min Dominating Set approximability gap

Informal conjecture on MIS approximability vs. Min Dominating Set · arXiv:2007.14161

arXiv Informal medium confidence— first stated 2021-02-12

Authors: Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant

Status partial high confidence

The 2022/2023 paper by Bergé, Bonnet, Déprés, and Watrigant (arXiv:2207.07708, STACS 2023) directly addresses MIS approximability on bounded twin-width graphs, establishing a polynomial-time n^ε-approximation algorithm and a time–approximation tradeoff (O(1)^{2^q-1}-approximation in time exp(O_q(n^{2^{-q}}))). This confirms that MIS sits in a strictly worse approximability regime than Min Dominating Set (which admits an O(1)-approximation) on bounded twin-width graphs, supporting the conjecture. However, no hardness result ruling out a constant-factor approximation for MIS on bounded twin-width has been established, so the precise approximability boundary remains open.

Cited literature (1)

partial Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width (2023)

Pierre Bergé, Édouard Bonnet, Hugues Déprés, Rémi Watrigant · 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), LIPIcs vol. 254 · arXiv:2207.07708 · doi:10.4230/LIPIcs.STACS.2023.10

Proves a polynomial-time n^ε-approximation and a time–approximation tradeoff for Max Independent Set on bounded twin-width graphs (given an O(1)-sequence), demonstrating that MIS is in a strictly worse approximability regime than Min Dominating Set (O(1) approximation), thereby providing the strongest published evidence that the two problems have fundamentally different approximability status on these graphs.

Reviewer notes. The conjecture is informal and has no precise mathematical statement to be proved or disproved; rather it asserts that MIS 'may' have a different approximability regime from Min DS. The STACS 2023 paper (arXiv:2207.07708) confirms the different regime in the sense that MIS achieves only n^ε approximation while Min DS achieves O(1), and notes this is the 'first in-depth study of approximability on bounded twin-width.' No polynomial-time constant-factor approximation for MIS is known, and no APX-hardness for MIS on bounded twin-width has been established, leaving the precise complexity boundary open.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. Max Independent Set may have a very different approximability status than Min Dominating Set on bounded twin-width graphs.

Context

Theorem 6 establishes $O(1)$-approximation algorithms for Min Dominating Set and Min $r$-Dominating Set on bounded twin-width graphs, but Max Independent Set (Distance-1 MIS) is explicitly excluded from that theorem. The authors note further that a constant approximation for Max Independent Set on bounded twin-width graphs with arbitrarily large clique number would imply a PTAS, and they give some evidence that MIS sits in a fundamentally different approximability regime.

Notes. PDF source — the full paper text is truncated after the beginning of the Related Work section; additional labeled conjecture/problem/question environments present in later sections of the paper are not visible in the provided extract and cannot be extracted.

Source paper

Twin-width III: Max Independent Set, Min Dominating Set, and Coloring
Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant · 2021-02-12
https://arxiv.org/abs/2007.14161 PDF source