# Is there any problem in $\mathsf{\Sigma^P_2}$ which is solvable in bounded tree width graphs?

I'm looking for a problem which belongs to $\mathsf{\Sigma^P_2}$ in general graphs but is in $\mathsf{P}$ in bounded tree width graphs, In fact I think this problems are harder than using normal dynamic programming in bounded-treewidth graphs to solve them.

• If the problem is in P for bounded-treewidth graphs, why do you say it's "harder than using normal DP" in such graphs ? Oct 17 '11 at 20:30

List Chromatic Number (Is it true that the graph has a vertex coloring whenever every vertex gets a list of k admissible colors?) is a $\Pi_2^P$-complete problem, but linear-time solvable on bounded-treewidth graphs:
• I think you mean $\exists X_1, \dots, X_k: (\text{IsPartition}(X_1, \dots, X_k) \land \forall X: (\text{MaxClique}(X) \implies \lnot(\exists X_i: \forall x\in X: x\in X_i)))$ Oct 18 '11 at 13:05