Independent Set Hardness in Graphs of Bounded Twin-Width and Low-Radius Merge-Width

Édouard Bonnet, Maël Dumas, Julien Duron

For every $\epsilon >0$, Max Independent Set admits a polynomial-time $n^{\epsilon }$-approximation algorithm on $n$-vertex graphs of effectively bounded twin-width [Bergé et a…