Para quais famílias de gráficos a Geografia Generalizada está em

Como o @Marzio mencionou, o jogo a seguir é conhecido como Geografia Generalizada .

Dado um gráfico e um vértice inicial , o jogo é definido da seguinte forma:$G=(V,E)$$v \in V$

A cada turno (dois jogadores alternando), um jogador escolhe e, em seguida, acontece o seguinte:$u\in N(v)$

1. $v$ , bem como todos os seus bordos, é removida a partir de .$G$
2. $u\to v$ (ou seja, é atualizado para ser o vértice ).$v$$u$

O jogador que é forçado a selecionar um "beco sem saída" (ou seja, um vértice sem arestas de saída) perde.

Em quais famílias de gráficos a estratégia ideal é computável em tempo polinomial?

Por exemplo, é fácil ver que, se é um DAG, podemos calcular facilmente a estratégia ideal para os jogadores.$G$

A Geografia Generalizada (GG) é completa no PSPACE, mesmo em gráficos bipartidos direcionados planares, mas, conforme relatado em:

Hans L. Bodlaender, Complexidade dos jogos de formação de caminhos , Ciência da Computação Teórica, Volume 110, Edição 1, 15 de março de 1993, Páginas 215-245

GG (e algumas outras variantes completas do PSPACE) são linearmente resolvíveis no tempo em gráficos de largura de árvore limitada.

NOTA LATERAL: uma das variantes da Geografia Generalizada que recentemente se mostrou completa no PSPACE é Tron ( jogo Light Cycles ): dado um gráfico não direcionado, dois jogadores escolhem dois vértices iniciais diferentes e depois se revezam, movendo-se para um adjacente vértice do respectivo respectivo anterior em cada etapa. O jogo termina quando os dois jogadores não podem mais se mover. O jogador que atravessou mais vértices vence (foi considerado um PSPACE completo em 1990 por Bodlaender e Kloks).
Tillmann Miltzow, Tron, um jogo combinatório em gráficos abstratos (2011)

$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, a mesma matriz é obtida se o jogador A puder escolher um nó inicial arbitrário.

Como dito nos comentários, acho que a complexidade de decidir se existe uma estratégia vencedora quando o GG é jogado em gráficos sólidos (com formas arbitrárias, mas sem buracos) não é conhecida e, provavelmente, não é tão fácil provar algo sobre isso. (na verdade, o problema - de certa forma relacionado - de decidir se um gráfico de grade sólido tem um caminho hamiltoniano ainda está aberto, embora decidir se um gráfico de grade sólido tem um ciclo hamiltoniano é solucionável em tempo polinomial).

Uma nota trivial final: GG também pode ser resolvido no tempo polinomial em gráficos completos.

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