Abstract
For every $\varepsilon > 0$, Max Independent Set has a polynomial-time $n^{\varepsilon}$-approximation algorithm on $n$-vertex graphs of effectively bounded twin-width [Bergé et al., STACS '23]. The approximation factor obtained is more precisely $n^{O(1/ \log \log n)}$. Prior to this paper, no approximation hardness was known for this problem, and the existence of a polynomial-time approximation scheme (PTAS) was repeatedly raised as an open question.
We answer this question in a strong sense: We show that there exists a constant $\gamma > 0$ such that a polynomial-time $n^{\gamma/ (\log \log n)^2}$-approximation algorithm for Max Independent Set on graphs of twin-width at most 4 would refute the Exponential-Time Hypothesis (ETH). This lower bound also holds if a 4-sequence is provided as part of the input.
We demonstrate the same hardness of approximation for Min Coloring, which also has a nearly matching $n^{O(1/ \log \log n)}$-approximation algorithm on effectively bounded twin-width graphs. Additionally, we clarify the parameterized complexity of $k$-Independent Set on graphs with bounded radius-$r$ merge-width when the range of $r$ is limited.
There is a fixed-parameter tractable algorithm for $k$-Independent Set on graphs given with radius $2^{O(k^2)}$ merge sequences of bounded width [Dreier and Toruńczyk, STOC '25]. We complement this result by showing that $k$-Independent Set is W[1]-hard on graphs given with radius $o(k)$ merge sequences of bounded width. This result also holds for $k$-Dominating Set.
Blogger's Review: This study reveals the approximation hardness of the independent set problem under specific structural constraints, providing new theoretical evidence supporting the validity of the Exponential-Time Hypothesis, and further enhances the understanding of parameterized complexity in graphs. The findings are significant not only for the independent set problem but also for minimum coloring and related issues.