Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 15 down vote favorite

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.

share|improve this question
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 Answers

up vote 8 down vote accepted

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

share|improve this answer
Very nice thanks, it seems it's better than David answer for me, let me read it. – Saeed Oct 20 '11 at 19:57
3  
If you like this result then maybe you're also intested in the following paper: 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 8:55
up vote 13 down vote

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.

share|improve this answer
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 7: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)))$ – JɛffE Oct 18 '11 at 13:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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