¿Se han resuelto estos juegos de colorear?

12

En el documento "Sobre la complejidad de algunos juegos de colorear", Bodlaender ofrece algunas preguntas abiertas sobre la complejidad de decidir si el jugador 1 o 2 tiene una estrategia ganadora en algunos juegos de colorear gráficos. ¿Alguien sabe si se han resuelto?

1) En un juego, dos jugadores se turnan para seleccionar un vértice en un gráfico y colorearlo adecuadamente con un color de un conjunto finito fijo. El perdedor es el primer jugador que no puede colorear un vértice. En el artículo de Schaefer se muestra que está completo en pspace con 1 color y Bodlaender muestra que está completo en pspace con 2 colores, pero no responde con más color. ¿Sigue abierto?

2) En otra variación, los vértices tienen números 1..n. En el turno de un jugador, debe colorear correctamente el vértice con el número más bajo que aún no se ha coloreado. Nuevamente, están usando colores de un conjunto fijo y el perdedor es el primer jugador que no puede colorear su vértice. Bodlaender muestra que es pspace-complete para gráficos generales. Pregunta quién gana en los árboles, ¿se sabe?

Gracias

graph-colouring pspace two-player-games usuario32149
fuente
2
¿Por qué no le preguntas directamente a Bodlaender? staff.science.uu.nl/~bodla101
Gamow

Respuestas:

2

Parece que este documento tiene algo de lo que estás buscando: http://arxiv.org/abs/1202.5762

La forma general de la primera pregunta es una reducción realmente simple: usando los colores {0, ..., n-1}, comience con una instancia de Node Kayles y cree un vértice para cada uno de los colores de 1 a n-1 y conéctese ellos a cada vértice incoloro. Ahora esos colores no se pueden jugar y todavía estás jugando el juego Node Kayles.

Kyle
fuente
Gracias por el enlace, voy a echar un vistazo. En esta pregunta, no permitimos un 'pre-coloreado', por lo que no podemos suponer que algunos vértices ya tienen un color. El juego comienza con todos los vértices sin color.
user32149
Eso tiene sentido, pero cambia la cuestión de la dureza. Para muchos juegos, se sabe qué jugador tiene una estrategia ganadora desde una posición inicial, pero no se sabe qué jugador tiene una estrategia ganadora en una posición general. Tome Hex por ejemplo. Aquí el primer jugador tiene una estrategia ganadora. Desde una posición general, determinar si el próximo jugador en moverse tiene una estrategia ganadora es PSPACE completo.
Kyle
Sí, tienes razón, debería haber aclarado en la pregunta original. Estoy hablando de la complejidad computacional de determinar quién gana en un gráfico dado antes de que se hayan coloreado los vértices.
user32149
Es una pregunta interesante, para estar seguro. Especialmente porque estás hablando de un gráfico general y no estás poniendo ningún requisito en su estructura. ¡Sin duda me interesará saber si te das cuenta!
Kyle