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.

Improve this question
$\endgroup$
2
  • $\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, 2015 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, 2015 at 16:35

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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