Feedback Game on Eulerian Graphs

Discrete and Computational Geometry, Graphs, and Games

Abstract

In this paper, we introduce a two-player impartial game on graphs, called feedback game, which is a variant of generalized geography. Feedback game can be regarded as undirected edge geography with an additional rule that the first player who goes back to the starting vertex wins the game. We consider feedback game on an Eulerian graph since the game ends only by going back to the starting vertex. We first show that it is PSPACE-complete in general to determine the winner of the feedback game on Eulerian graphs even if its maximum degree is at most~4. In the latter half of the paper, we discuss the feedback game on two subclasses of Eulerian graphs, i.e., triangular grid graphs and toroidal grid graphs.