Deciding twin-width at most 4 is NP-complete.

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

Published in: CoRR (2021)

Keyphrases

np complete
np hard
randomly generated
constraint satisfaction problems
satisfiability problem
computational complexity
np complete problems
data complexity
pspace complete
conjunctive queries
fixed width
constraint satisfaction
normal form
phase transition
polynomial time complexity