Für welche Graphenfamilien gilt Generalized Geography in

Wie @Marzio erwähnte, ist das folgende Spiel als Generalized Geography bekannt .

Bei einem Graphen und einem Startscheitelpunkt v ∈ V ist das Spiel wie folgt definiert:$G=(V,E)$$v \in V$

In jeder Runde (zwei Spieler wechseln sich ab) wählt ein Spieler , und dann passiert Folgendes:$u\in N(v)$

1. sowie alle seine Kanten werden aus G entfernt .$v$$G$
2. (dh v wird aktualisiert, um der Scheitelpunkt u zu sein ).$u\to v$$v$$u$

Der Spieler, der gezwungen ist, eine "Sackgasse" (dh einen Scheitelpunkt ohne ausgehende Kanten) auszuwählen, verliert.

In welchen Graphenfamilien ist die optimale Strategie in der Polynomzeit berechenbar?

Zum Beispiel ist es leicht zu erkennen, dass wir , wenn eine DAG ist, leicht die optimale Strategie für die Spieler berechnen können.$G$

Generalized Geography (GG) ist PSPACE-vollständig, selbst auf planar gerichteten zweigeteilten Graphen, aber wie in:

Hans L. Bodlaender, Komplexität pfadbildender Spiele , Theoretische Informatik, Band 110, Ausgabe 1, 15. März 1993, Seiten 215-245

GG (und einige andere PSPACE-vollständige Varianten) sind in Graphen mit begrenzter Baumbreite linear zeitlösbar.

SEITLICHER HINWEIS: Eine der Varianten von Generalized Geography, die sich kürzlich als PSPACE-vollständig erwiesen hat, ist Tron ( Light Cycles- Spiel): Bei einem ungerichteten Diagramm wählen zwei Spieler zwei verschiedene Startscheitelpunkte aus und wechseln sich dann ab, indem sie sich zu einem benachbarten bewegen Scheitelpunkt von ihrem jeweiligen vorherigen in jedem Schritt. Das Spiel endet, wenn sich beide Spieler nicht mehr bewegen können. Der Spieler, der mehr Eckpunkte durchquert hat, gewinnt (Bodlaender und Kloks vermuteten 1990, dass PSPACE vollständig ist).
Tillmann Miltzow, Tron, ein kombinatorisches Spiel über abstrakte Graphen (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 

Seltsamerweise wird dieselbe Matrix erhalten, wenn Spieler A einen beliebigen Startknoten auswählen kann.

Wie in den Kommentaren erwähnt, ist die Komplexität der Entscheidung, ob es eine Gewinnstrategie gibt, wenn GG auf soliden Gittergraphen (mit beliebigen Formen, aber ohne Löcher) gespielt wird , meiner Meinung nach nicht bekannt und es ist wahrscheinlich nicht so einfach, etwas zu beweisen es (in der Tat ist das - etwas verwandte - Problem der Entscheidung, ob ein Vollgittergraph einen Hamilton- Pfad hat, noch offen, obwohl die Entscheidung, ob ein Vollgittergraph einen Hamilton- Zyklus hat, polynomial lösbar ist).

Eine letzte triviale Anmerkung: GG ist polynomiell zeitlösbar, auch in vollständigen Graphen.

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