Ces jeux de coloriage ont-ils été résolus?

12

Dans l'article "Sur la complexité de certains jeux de coloriage", Bodlaender pose quelques questions ouvertes sur la complexité de décider si le joueur 1 ou 2 a une stratégie gagnante dans certains jeux de coloriage de graphiques. Est-ce que quelqu'un sait s'ils ont été résolus?

1) Dans une partie, deux joueurs choisissent à tour de rôle un sommet dans un graphique et le colorent correctement avec une couleur d'un ensemble fini fixe. Le perdant est le premier joueur incapable de colorer un sommet. Dans l'article de Schaefer, il est montré que pspace-complete avec 1 couleur et Bodlaender montre qu'il est pspace-complete avec 2 couleurs mais ne donne aucune réponse avec plus de couleur. Est-il toujours ouvert?

2) Dans une autre variante, les sommets ont des nombres 1..n. Au tour d'un joueur, il doit colorer correctement le sommet avec le plus petit nombre qui n'a pas encore été coloré. Encore une fois, ils utilisent des couleurs d'un ensemble fixe et le perdant est le premier joueur qui n'est pas en mesure de colorer son sommet. Bodlaender montre qu'il est pspace-complete pour les graphiques généraux. Il demande qui gagne sur les arbres, est-ce connu?

Merci

graph-colouring pspace two-player-games user32149
la source
2
Pourquoi ne demandez-vous pas directement à Bodlaender? staff.science.uu.nl/~bodla101
Gamow

Réponses:

2

Il semble que ce document contient une partie de ce que vous recherchez: http://arxiv.org/abs/1202.5762

La forme générale de la première question est une réduction très simple: en utilisant les couleurs {0, ..., n-1}, commencez par une instance de Node Kayles et créez un sommet pour chacune des couleurs de 1 à n-1 et connectez les à chaque sommet incolore. Maintenant, ces couleurs ne peuvent pas être jouées et vous jouez toujours au jeu Node Kayles.

Kyle
la source
Merci pour le lien, je vais y jeter un œil. Dans cette question, nous n'autorisons pas une «pré-coloration», nous ne sommes donc pas autorisés à supposer que certains sommets ont déjà une couleur. Le jeu commence avec tous les sommets non colorés.
user32149
Cela a du sens, mais cela change la question de la dureté. Pour de nombreux jeux, on sait quel joueur a une stratégie gagnante à partir d'une position initiale, mais on ne sait pas quel joueur a une stratégie gagnante à une position générale. Prenez Hex par exemple. Ici, le premier joueur a une stratégie gagnante. À partir d'une position générale, déterminer si le prochain joueur à se déplacer a une stratégie gagnante est PSPACE-complete.
Kyle
Oui, vous avez raison, j'aurais dû clarifier la question d'origine. Je parle de la complexité informatique de déterminer qui gagne sur un graphique donné avant que les sommets aient été colorés.
user32149
C'est une question intéressante, bien sûr. D'autant plus que vous parlez d'un graphe général et n'imposez aucune exigence à sa structure. Je serai certainement intéressé de savoir si vous le comprenez!
Kyle