16
$\begingroup$

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.

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

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

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Bart Jansen Oct 21 '11 at 8:55
13
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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))))) $\endgroup$ – M. kanté Oct 18 '11 at 7:04
  • 2
    $\begingroup$ 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)))$ $\endgroup$ – Jeffε Oct 18 '11 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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