¿Para qué familias de gráficos es Geografía generalizada en ?

Como mencionó @Marzio, el siguiente juego se conoce como Geografía Generalizada .

Dado un gráfico y un vértice inicial , el juego se define de la siguiente manera:v ∈ $G=(V,E)$$v \in V$

En cada turno (dos jugadores alternando), un jugador elige $u\in N(v)$ , y luego sucede lo siguiente:

1. $v$ , así como todos sus bordes, se retira de $G$ .
2. $u\to v$ (es decir, $v$ se actualiza para ser el vértice $u$ ).

El jugador que se ve obligado a seleccionar un "callejón sin salida" (es decir, un vértice sin bordes salientes) pierde.

¿En qué familias de gráficos es la estrategia óptima computable en tiempo polinómico?

Por ejemplo, es fácil ver que si $G$ es un DAG, entonces podemos calcular fácilmente la estrategia óptima para los jugadores.

La geografía generalizada (GG) es completa para PSPACE incluso en gráficos bipartitos planos dirigidos, pero, como se informa en:

Hans L. Bodlaender, Complejidad de los juegos de formación de caminos , Ciencias de la Computación Teórica, Volumen 110, Número 1, 15 de marzo de 1993, Páginas 215-245

GG (y algunas otras variantes completas de PSPACE) se pueden resolver en tiempo lineal en gráficos de ancho de árbol acotado.

NOTA LATERAL: una de las variantes de Geografía Generalizada que recientemente se ha demostrado que completa PSPACE es Tron ( juego de Light Cycles ): dado un gráfico no dirigido, dos jugadores eligen dos vértices iniciales diferentes y luego se turnan, moviéndose a un adyacente vértice de su respectivo anterior en cada paso. El juego termina cuando ambos jugadores ya no pueden moverse. El jugador que atravesó más vértices gana (se conjetura que fue completado por PSPACE en 1990 por Bodlaender y Kloks).
Tillmann Miltzow, Tron, un juego combinatorio sobre gráficos abstractos (2011)

Editar : Hice un pequeño programa para probar el juego en pequeños gráficos de cuadrícula sólida rectangular (no dirigido), y el resultado sugiere que también es solucionable en tiempo polinómico para esta clase de gráficos (suponiendo que el primer nodo elegido por el jugador A es el nodo superior izquierdo):$n \times m$

               Width n
           1 2 3 4 5 6 7 8 
         1 A B A B A B A B    Winning matrix up to 8x8
         2   B B B B B B B 
         3     A B A B A B 
Height m 4       B B B B B  
         5         A B A B 
         6           B B B 
         7             A B 
         8               B 

Curiosamente, se obtiene la misma matriz si el jugador A puede elegir un nodo inicial arbitrario.

Como se dijo en los comentarios, creo que no se conoce la complejidad de decidir si hay una estrategia ganadora cuando se juega GG en gráficos de cuadrícula sólidos (con formas arbitrarias, pero sin agujeros) y probablemente no sea tan fácil demostrar algo sobre (de hecho, el problema, algo relacionado) de decidir si un gráfico de cuadrícula sólida tiene un camino hamiltoniano todavía está abierto, aunque decidir si un gráfico de cuadrícula sólida tiene un ciclo hamiltoniano es tiempo polinómico solucionable).

Una nota trivial final: GG es tiempo polinómico solucionable también en gráficos completos.

$1$$c$$G-c$$0$$c$$1$