We show that many non-MSO1 NP-hard graph problems can be solved in polynomial time on clique-width and NLC-width bounded graphs using a very general
and simple scheme. Our examples are partition into cliques, partition into triangles, partition into complete bipartite subgraphs,
partition into perfect matchings, partition into forests, cubic subgraph, Hamiltonian path, minimum maximal matching, and
vertex/edge separation problems.
The work of the second author was supported by the German Research Association (DFG) grant WA 674/9-1.