5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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" ? $\endgroup$ – Konstantinos Koiliaris Jul 22 '15 at 16:26
  • $\begingroup$ @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. $\endgroup$ – Kumar Jul 22 '15 at 16:35
8
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.