Pour quelles familles de graphiques la géographie généralisée est-elle en ?

Comme @Marzio l'a mentionné, le jeu suivant est connu sous le nom de Géographie généralisée .

Étant donné un graphique et un sommet de départ , le jeu est défini comme suit:$G=(V,E)$$v \in V$

A chaque tour (alternance de deux joueurs), un joueur choisit $u\in N(v)$ , puis ce qui suit se produit:

1. $v$ , ainsi que l' ensemble de ses bords, est retiré de $G$ .
2. $u\to v$ (c'est-à-dire que $v$ est mis à jour pour être le sommet $u$ ).

Le joueur qui est obligé de sélectionner une "impasse" (c'est-à-dire un sommet sans bords sortants) perd.

Dans quelles familles de graphes la stratégie optimale est-elle calculable en temps polynomial?

Par exemple, il est facile de voir que si $G$ est un DAG, alors nous pouvons facilement calculer la stratégie optimale pour les joueurs.

La géographie généralisée (GG) est complète sur PSPACE même sur les graphes bipartis dirigés planaires, mais, comme indiqué dans:

Hans L. Bodlaender, Complexity of path-making games , Theoretical Computer Science, Volume 110, Numéro 1, 15 mars 1993, Pages 215-245

GG (et quelques autres variantes complètes de PSPACE) sont solubles dans le temps linéaire dans les graphiques de largeur d'arbre bornée.

NOTE LATÉRALE: Tron ( jeu Light Cycles ) est l' une des variantes de la géographie généralisée qui s'est récemment révélée complète pour PSPACE : étant donné un graphique non orienté, deux joueurs choisissent deux sommets de départ différents, puis se relaient, en se déplaçant vers un emplacement adjacent sommet de leur précédent respectif à chaque étape. Le jeu se termine lorsque les deux joueurs ne peuvent plus bouger. Le joueur qui a traversé plus de sommets gagne (il a été supposé être PSPACE-complete en 1990 par Bodlaender et Kloks).
Tillmann Miltzow, Tron, un jeu combinatoire sur les graphes abstraits (2011)

Edit : J'ai fait un petit programme pour tester le jeu sur de petits graphiques à grille solide rectangulaire (non orientés ), et le résultat suggère qu'il est également possible de résoudre le temps polynomial pour cette classe de graphiques (en supposant que le premier nœud choisi par le joueur A est le nœud en haut à gauche):$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 

Curieusement, la même matrice est obtenue si le joueur A peut choisir un nœud de départ arbitraire.

Comme dit dans les commentaires, je pense que la complexité de décider s'il y a une stratégie gagnante lorsque GG est joué sur des graphiques à grille solide (avec des formes arbitraires, mais sans trous) n'est pas connue et il n'est probablement pas si facile de prouver quelque chose il (en effet le problème - quelque peu connexe - de décider si un graphe de grille solide a un chemin hamiltonien est toujours ouvert, bien que décider si un graphe de grille solide a un cycle hamiltonien est résolu en temps polynomial).

Une dernière remarque triviale: GG est résolvable en temps polynomial également dans les graphiques complets.

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