Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width

Pierre Bergé, Édouard Bonnet, Hugues Déprés +1

For any $\epsilon >0$, we give a polynomial-time $n^{\epsilon }$-approximation algorithm for Max Independent Set in graphs of bounded twin-width given with an $O(1)$-sequence.…