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 , 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)$

, jak również wszystkich brzegów, jest usuwany z . $v$ $G$
(tzn. jest zaktualizowany do wierzchołka ). $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$

graph-theory graph-algorithms gt.game-theory

— RB
źródło

Gra jest znana jako Uogólniona Geografia i jest ukończona w PSPACE (nawet na wykresach planarnych). Zobacz gry Complexity of Path Forming dla niektórych wariantów (także niektóre warianty wielomianowe)

— Marzio De Biasi

Czy mógłbyś to sprecyzować? Np. Z linku Marzio widać, że ograniczona szerokość jest wystarczająca.

— domotorp

@domotorp: Myślę, że GG na niekierowanych grafach o stałej siatce jest nierozwiązanym otwartym problemem (być może również nie badanym). Zajmę się trochę Google, aby zobaczyć, czy to nowy problem. Podczas gdy w przypadku ukierunkowanych grafów z pełnymi siatkami wydaje się, że łatwo jest symulować „dziury” przy użyciu ukierunkowanych krawędzi, więc powinna być kompletna z PSPACE.

— Marzio De Biasi

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.

— Marzio De Biasi
źródło

Czy jesteś pewien, że cykl hamiltonowski na wykresie w postaci stałej siatki jest rozwiązaniem czasu wielomianowego? Z tego, co pamiętam, po prostu nie wiadomo, z drugiej strony, jeśli ta stała siatka ma jakieś struktury (jak kształt L, kształt T, mxn, ...), to jest to czas wielomianowy do rozwiązania, ale nie pamiętam żadnego papieru, który rozwiązałby go w czasie wielomianowym ogólnie wykresy z jednolitą siatką. Czy masz referencje?

— Saeed

@ Saeed Wygląda na to, że Umans i Lenhart rozwiązali długotrwały otwarty problem, patrz Cykle Hamiltona na solidnych wykresach siatki . Kilka razy temu szukałem najnowszych / powiązanych wyników dotyczących ścieżki Hamiltona na wykresach siatki stałej, ale nic nie znalazłem. (Wydaje mi się, że istnieje również powiązane pytanie dotyczące cstheory)

— Marzio De Biasi

Dzięki, to naprawdę świetne, a także niezbyt nowy FOCS1997 , ale nigdy go nie widziałem!

— Saeed

Świetna odpowiedź @MarzioDeBiasi. Właściwie natknąłem się na ten problem w innym otoczeniu, które można modelować jako wykres siatki, ale byłem również ciekawy jego uogólnienia.

— RB

Spędziłem pół godziny, ale nie mogłem znaleźć żadnych odniesień do Nieukierunkowanej Ogólnej Geografii. Jestem pewien, że ktoś musiał pokazać, że jest kompletny z PSPACE. Czy wiesz o tym?

— domotorp

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

— Saeed
źródło