Acyclic Geography Game (AGG)
Category: Games
Input
An acyclic directed graph $G = (V, E)$.
Problem
Does player one have a winning strategy on $G$?
Description
The Acyclic Geography Game is played on $G$ by two players. A configuration of the game is a vertex $u \in V$. Players take turns choosing an edge $(u, v) \in G$, thereby changing the game configuration from $u$ to $v$. The initial configuration is $u = 1$. The first player with no move left loses.
Status
$\P$-complete (Chandra and Tompa [1]).
Remarks
The reduction to show hardness is from MCVP. Chandra and Tompa show that a depth constrained version of the Geography Game, called SHORTGEOG, is complete for $\mathsf{AC}^1$ [1].