In this paper we show that a very wide class of optimization problems, namely the class of LinEMSOL($\tau_{1,L}$) problems is solvable in linear time on the class of extended $P_4$-sparse graphs. Roughly speaking, LinEMSOL($\tau_{1,L}$) is the class of problems which can be expressed as the search for sets of vertices which are optimal with respect to some linear evaluation function and a monadic second order formula $\theta$.
The class of graphs of clique-width at most $k$ was introduced by Courcelle as the class of graphs which can be defined by expressions based on graph operations which use $k$ vertex labels. In this paper we show that the class of extended $P_4$-sparse graphs is a subclass of the class of graphs of clique-width at most 4. Furthermore, we show, generalizing our result on $P_4$-sparse graphs, that the class of LinEMSOL($\tau_{1,L}$) optimization problems is solvable in $O(f(|V|,|E|))$ time on a class of graphs of clique-width at most $k$ in which for every graph $G$ an expression defining it can be constructed in $O(f(|V|,|E|))$ time.
Finally, we show that the above results cannot be extended to MSOL($\tau_2$) decision and optimization problems on the vocabulary $\tau_2$ which allow edges to be considered as elements of the domains of the graphs in question, and by that, allow quantifying over edges in addition to quantifying over vertices. In particular we show that if $\bP_1 \neq \bNP_1$ then there is a $MSOL(\tau_{2})$ definable decision problem on cliques which is not solvable in polynomial time. Here $\bP_1$ ($\bNP_1$) denotes the class of languages over one letter (also called tally languages), which are in $\bP$ ($\bNP$).