Clique-width minimization is NP-hard.

Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider

Browse the full STOC paper archive.