Deciding twin-width at most 4 is NP-complete

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

We show that determining if an $n$-vertex graph has twin-width at most 4 is NP-complete, and requires time $2^{\Omega (n/\log n)}$ unless the Exponential-Time Hypothesis fails. Along the…