Dla których rodzin grafów jest uogólniona geografia w

Jak wspomniano @Marzio, następująca gra jest znana jako Geografia uogólniona .

Biorąc pod uwagę wykres i początkowy wierzchołek v ∈ V , grę definiuje się w następujący sposób:$G=(V,E)$$v \in V$

W każdej turze (dwóch graczy na przemian) gracz wybiera , a następnie dzieje się tak:$u\in N(v)$

1. , jak również wszystkich brzegów, jest usuwany z G .$v$$G$
2. (tzn. v jest zaktualizowany do wierzchołka u ).$u\to v$$v$$u$

Gracz, który jest zmuszony wybrać „ślepy zaułek” (tj. Wierzchołek bez krawędzi wychodzących) przegrywa.

W których rodzinach grafów można obliczać optymalną strategię w czasie wielomianowym?

Na przykład łatwo zauważyć, że jeśli jest DAG, możemy łatwo obliczyć optymalną strategię dla graczy.$G$

Geografia uogólniona (GG) jest kompletna z PSPACE nawet na dwustronnych grafach kierowanych na płaszczyznę, ale jak podano w:

Hans L. Bodlaender, Złożoność gier formujących ścieżki , Theoretical Computer Science, tom 110, wydanie 1, 15 marca 1993, strony 215-245

GG (i niektóre inne warianty kompletne z PSPACE) można rozwiązać w czasie liniowym na wykresach ograniczonej szerokości.

UWAGA BOCZNA: jednym z wariantów uogólnionej geografii, które niedawno okazało się być kompletne dla PSPACE, jest Tron ( gra Light Cycles ): biorąc pod uwagę niekierowany wykres, dwóch graczy wybiera dwa różne początkowe wierzchołki, a następnie na zmianę, przechodząc do sąsiedniego wierzchołek od ich poprzedniego poprzedniego w każdym kroku. Gra kończy się, gdy obaj gracze nie mogą się już poruszać. Gracz, który przemierzył więcej wierzchołków wygrywa (Bodlaender i Kloks przypuszczali, że w 1990 r. Ukończył PSPACE).
Tillmann Miltzow, Tron, gra kombinatoryczna na abstrakcyjnych wykresach (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 

Co ciekawe, tę samą macierz uzyskuje się, jeśli gracz A może wybrać dowolny węzeł początkowy.

Jak powiedziano w komentarzach, myślę, że złożoność decydowania, czy istnieje strategia wygrywająca, gdy GG jest odtwarzana na solidnych grafach siatki (o dowolnych kształtach, ale bez otworów), nie jest znana i prawdopodobnie nie jest tak łatwo udowodnić coś o to (rzeczywiście - nieco spokrewniony) problem decydowania o tym, czy wykres stałej siatki ma ścieżkę hamiltonowską, jest nadal otwarty, choć podejmowanie decyzji, czy wykres stałej siatki ma cykl hamiltonowski , jest rozwiązaniem wielomianowym.

Ostatnia trywialna uwaga: GG rozwiązuje czas wielomianowy również na pełnych wykresach.

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