Y a-t-il un problème dans qui peut être résolu dans les graphiques de largeur d'arbre borné?

16

Je cherche un problème qui appartient à dans les graphiques généraux mais qui est dans dans les graphiques de largeur d'arbre borné, En fait, je pense que ces problèmes sont plus difficiles que d'utiliser la programmation dynamique normale dans borné -des graphiques de largeur pour les résoudre. $\mathsf{\Sigma^P_2}$ $\mathsf{P}$

cc.complexity-theory graph-theory treewidth Saeed
la source

Si le problème est dans P pour les graphiques à largeur d'arbre bornée, pourquoi dites-vous que c'est "plus difficile que d'utiliser DP normal" dans de tels graphiques?

Suresh Venkat

11

List Chromatic Number (Est-il vrai que le graphique a une coloration de sommet chaque fois que chaque sommet obtient une liste de k couleurs admissibles?) Est un problème -complet, mais résolu en temps linéaire sur les graphiques à largeur d'arbre borné: $\Pi_2^P$

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

Daniel Marx
la source

3

Si vous aimez ce résultat, peut-être que vous êtes également intéressé par l'article suivant: arxiv.org/abs/1110.4077 . Il est apparu sur l'arXiv cette semaine, et les auteurs montrent que le nombre chromatique de bord de liste et le nombre chromatique total de liste sont également solubles en temps linéaire pour les graphiques de largeur d'arbre borné.

Bart Jansen

13

Je pense que la coloration à 2 cliques [GT19 à Schaefer et Umans ] en est un exemple. La question est de savoir si le graphique donné peut être (incorrectement) bicolore de telle sorte qu'aucune de ses cliques maximales ne soit monochromatique. Pour les graphiques de largeur d'arbre bornée, chaque clique maximale doit se produire dans un seul sac de la décomposition de l'arbre, donc cela devrait fonctionner pour utiliser l'approche de programmation dynamique standard dans laquelle les états du programme dynamique sont 2 couleurs du sac qui colorent correctement tous cliques maximales dans le sac et sont conformes aux bons états des sacs pour enfants.

David Eppstein
la source

1

Il est en P pour TW (<= k) aussi pour cette raison: la coloration de la k-clique est MS-expressible: "Existe X_1, ... X_k (Partition (X_1, ..., X_k) et ForAll X (CliqueMax (X) => pas (Existe X_i (Forall x dans X (x dans X_i))))))

M. kanté

2

Je pense que vous voulez dire

\exists X_{1}, \dots, X_{k} : (IsPartition (X_{1}, \dots, X_{k}) \land \forall X : (MaxClique (X) ⟹ \neg (\exists X_{i} : \forall x \in X : x \in X_{i})))

$\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ε

Y a-t-il un problème dans qui peut être résolu dans les graphiques de largeur d'arbre borné?

Réponses: