17

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.

Saeed
  • 3,440
  • 1
  • 22
  • 39
  • If the problem is in P for bounded-treewidth graphs, why do you say it's "harder than using normal DP" in such graphs ? – Suresh Venkat Oct 17 '11 at 20:30

2 Answers2

13

I think 2-clique-coloring [GT19 in Schaefer and Umans] is an example. The question is whether the given graph can be (improperly) 2-colored in such a way that none of its maximal cliques are monochromatic. For graphs of bounded treewidth, each maximal clique should occur within a single bag of the tree decomposition, so it should work to use the standard dynamic programming approach in which the states of the dynamic program are 2-colorings of the bag that correctly color all maximal cliques within the bag and are consistent with good states of the child bags.

David Eppstein
  • 50,990
  • 3
  • 170
  • 278
  • 1
    It is in P for TW(<=k) for also this reason: the k-clique colouring is MS-expressible: "Exists X_1,...X_k (Partition(X_1,...,X_k) and ForAll X(CliqueMax(X) => not (Exists X_i (Forall x in X( x in X_i))))) – M. kanté Oct 18 '11 at 07:04
  • 2
    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)))$ – Jeffε Oct 18 '11 at 13:05
11

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:

http://www.ii.uib.no/~daniello/papers/EqColoring.pdf

Daniel Marx
  • 1,978
  • 12
  • 12
  • 3
    If you like this result then maybe you're also intested in the following paper: http://arxiv.org/abs/1110.4077 . It appeared on the arXiv this week, and the authors show that List Edge Chromatic Number and List Total Chromatic Number are also linear-time solvable for graphs of bounded treewidth. – Bart Jansen Oct 21 '11 at 08:55