2021/08/20 by Fox, Nathan, Geissler, Carson
#05C57 (Secondary) #91A46 (Primary) 68Q17 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #F.1.3 #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.2108.09367
Generalized Geography is a combinatorial game played on a directed graph. Players take turns moving a token from vertex to vertex, deleting a vertex after moving the token away from it. A player unable to move loses. It is well known that the computational complexity of determining which player should win from a given position of Generalized Geography is PSPACE-complete. We introduce several rule variants to Generalized Geography, and we explore the computational complexity of determining the winner of positions of many resulting games. Among our results is a proof that determining the winner of a game known in the literature as Undirected Partizan Geography is PSPACE-complete, even when restricted to being played on a bipartite graph.