Для каких семейств графов это обобщенная география в ?

Как упомянул @Marzio, следующая игра называется Generalized Geography .

Для графа и начальной вершины игра определяется следующим образом:$G=(V,E)$$v \in V$

На каждом ходу (чередуются два игрока), игрок выбирает , и тогда происходит следующее:$u\in N(v)$

1. $v$ , а также все его края, удаляется из .$G$
2. $u\to v$ (то есть обновляется, чтобы быть вершиной ).$v$$u$

Игрок, который вынужден выбрать «тупик» (т. Е. Вершину без исходящих ребер), проигрывает.

В каких семействах графов оптимальная стратегия вычисляется за полиномиальное время?

Например, легко видеть, что если - DAG, то мы можем легко вычислить оптимальную стратегию для игроков.$G$

Обобщенная география (GG) является PSPACE-полной даже на плоских ориентированных двудольных графах, но, как сообщается в:

Ханс Л. Бодлендер, Сложность игр , формирующих путь , Теоретическая информатика, том 110, выпуск 1, 15 марта 1993 г., страницы 215-245

GG (и некоторые другие PSPACE-полные варианты) линейно разрешимы во времени в графах ограниченной длины деревьев.

ПОБОЧНОЕ ПРИМЕЧАНИЕ: один из вариантов Обобщенной географии, который, как недавно было доказано, является PSPACE-полным, - это Tron ( игра Light Cycles ): по ненаправленному графику два игрока выбирают две разные начальные вершины, а затем по очереди переходят к соседней. вершина от их предыдущего предыдущего в каждом шаге. Игра заканчивается, когда оба игрока не могут больше двигаться. Игрок, который прошел больше вершин, выигрывает (Бодлендер и Клокс предположили, что он будет завершен в PSPACE в 1990 году).
Тильманн Мильцов, Трон, комбинаторная игра на абстрактных графах (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 

Любопытно, что та же самая матрица получается, если игрок А может выбрать произвольный начальный узел.

Как сказано в комментариях, я думаю, что сложность решения о том, существует ли выигрышная стратегия, когда GG воспроизводится на графиках со сплошной сеткой (с произвольными формами, но без дырок), неизвестна, и, вероятно, не так легко доказать что-либо о это (на самом деле - в некоторой степени связанная с этим - проблема принятия решения, если у графа со сплошной сеткой есть гамильтонов путь , еще открыт, хотя решение о том, имеет ли граф со сплошной сеткой гамильтоновый цикл , разрешимо за полиномиальное время).

Последнее тривиальное примечание: GG разрешимо за полиномиальное время и в полных графах.

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