# Example of $MSO_2$ definable NP-hard problem on bounded clique-width graphs

All $MSO_1$ and $MSO_2$ definable graph problems can be solved in linear time on bounded tree-width graphs by Courcelle's theorem. But it seems this theorem doesn't work for $MSO_2$ definable graph problems on bounded clique-width graphs.

Can some provide me an example of $MSO_2$ definable NP-hard problem on bounded clique-width graphs.

• I am guessing you mean to ask: "Provide an example of an $MSO_2$-expressible NP-hard problem that cannot be solved by Courcelle's Thm on bounded clique-width graphs" ? – Konstantinos Koiliaris Jul 22 '15 at 16:26
• @KXK In general many NP-hard graph problems are polynomial time solvable when we restrict them to graphs of some constant clique-width. I am looking for an example where the hardness of the problem still present even if the underlying graph has bounded clique-width. Hope it is clear. – Kumar Jul 22 '15 at 16:35

One example is the vertex disjoint paths problem, which is linear time solvable in graphs of bounded tree width but NPC in graphs of clique width at most $6$.