<p>One example is the vertex disjoint paths problem, which is linear time solvable in graphs of bounded tree width but <a href="http://www.sciencedirect.com/science/article/pii/S0304397506002003" rel="noreferrer">NPC in graphs of clique width at most $6$</a>.</p>

CC BY-SA 3.0
2015-07-22T17:53:54.413Z
2015-07-23T07:12:31.317Z
2015-07-23T07:12:31.317Z
Saeed
<p>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. </p>

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

CC BY-SA 3.0
2015-07-22T16:26:55.073Z
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
CC BY-SA 3.0
2015-07-22T16:35:47.917Z
@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
<lo.logic><cliquewidth>
Example of $MSO_2$ definable NP-hard problem on bounded clique-width graphs
Kumar
# Example of $MSO_2$ definable NP-hard problem on bounded clique-width graphs

(Asked by: username_0 on 2015-07-22)

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.

**Tags:** lo.logic, cliquewidth

> **Comments:**
> **username_1**: 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"* ?  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_2 on 2015-07-22. Score: 8 | Accepted answer

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$](http://www.sciencedirect.com/science/article/pii/S0304397506002003).


---

