Untuk keluarga grafik mana Generalised Geography di

Seperti yang disebutkan @Marzio, game berikut ini dikenal sebagai Generalized Geography .

Diberikan grafik dan simpul awal v ∈ V , permainan didefinisikan sebagai berikut:$G=(V,E)$$v \in V$

Di setiap belokan (dua pemain bergantian), seorang pemain memilih , dan kemudian terjadi hal berikut:$u\in N(v)$

1. , serta semua ujungnya, dihapus dari G .$v$$G$
2. (yaitu v diperbarui menjadi simpul u ).$u\to v$$v$$u$

Pemain yang dipaksa untuk memilih "jalan buntu" (yaitu titik tanpa tepi keluar) hilang.

Di mana grafik keluarga adalah strategi optimal yang dapat dihitung dalam waktu polinomial?

Misalnya, mudah untuk melihat bahwa jika adalah DAG, maka kita dapat dengan mudah menghitung strategi optimal untuk para pemain.$G$

Generalized Geography (GG) adalah PSPACE-complete bahkan pada grafik bipartit diarahkan planar, tetapi, seperti yang dilaporkan dalam:

Hans L. Bodlaender, Kompleksitas permainan pembentukan jalur , Ilmu Komputer Teoritis, Volume 110, Edisi 1, 15 Maret 1993, Halaman 215-245

GG (dan beberapa varian PSPACE-complete lainnya) adalah linear-time-solvable dalam grafik treewidth terikat.

CATATAN SISI: salah satu varian Generalized Geography yang baru-baru ini terbukti PSPACE-complete adalah Tron ( permainan Light Cycles ): diberi grafik yang tidak diarahkan, dua pemain memilih dua simpul awal yang berbeda, dan kemudian bergiliran, dengan pindah ke yang berdekatan simpul dari masing-masing sebelumnya di setiap langkah. Permainan berakhir ketika kedua pemain tidak bisa bergerak lagi. Pemain yang melintasi lebih banyak kemenangan simpul (itu diduga menjadi PSPACE-selesai pada tahun 1990 oleh Bodlaender dan Kloks).
Tillmann Miltzow, Tron, Game kombinatorial pada Grafik abstrak (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 

Anehnya, matriks yang sama diperoleh jika pemain A dapat memilih simpul awal yang sewenang-wenang.

Seperti yang dikatakan dalam komentar, saya berpikir bahwa kompleksitas memutuskan apakah ada strategi kemenangan ketika GG dimainkan pada grafik kotak solid (dengan bentuk acak, tetapi tanpa lubang) tidak diketahui dan mungkin tidak begitu mudah untuk membuktikan sesuatu tentang itu (memang - agak terkait - masalah memutuskan apakah grafik kotak solid memiliki jalur Hamilton masih terbuka, meskipun memutuskan apakah grafik kotak padat memiliki siklus Hamilton adalah waktu polinomial yang dapat dipecahkan).

Catatan terakhir yang sepele: GG adalah waktu polinomial yang dapat dipecahkan juga dalam grafik lengkap.

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