Independent Set Hardness in Graphs of Bounded Twin-Width and Low-Radius Merge-Width
2026-06-30 • Computational Complexity
Computational ComplexityDiscrete MathematicsData Structures and Algorithms
AI summaryⓘ
The authors study the difficulty of finding large independent sets and colorings in special graphs called those with bounded twin-width. They prove that getting very good approximations in polynomial time is likely impossible unless a major complexity assumption (ETH) fails, even when extra structural information is given. They also analyze the complexity of finding independent sets of size k in graphs with bounded merge-width and show hardness results depending on a parameter linked to the graph's structure. Their work clarifies limits on both approximation and parameterized algorithms in these graph classes.
Max Independent Setapproximation algorithmtwin-widthExponential-Time Hypothesis (ETH)graph coloringmerge-widthfixed-parameter tractabilityW[1]-hardnessparameterized complexitypolynomial-time approximation scheme (PTAS)
Authors
Édouard Bonnet, Maël Dumas, Julien Duron
Abstract
For every $\varepsilon > 0$, Max Independent Set admits a polynomial-time $n^\varepsilon$-approximation algorithm on $n$-vertex graphs of effectively bounded twin-width [Bergé et al., STACS '23]. The approximation factor actually obtained is more precisely $n^{O(1/ \log \log n)}$. Prior to the current 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 is a constant $γ> 0$ such that a polynomial-time $n^{γ/ (\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 further holds if a 4-sequence is provided as part of the input. We show the same hardness of approximation for Min Coloring, which also has a nearly matching $n^{O(1/ \log \log n)}$-approximation algorithm on graphs of effectively bounded twin-width. We also clarify the parameterized complexity of $k$-Independent Set on graphs of 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. We further show that this result also holds for $k$-Dominating Set.