Complexity proved hard for partizan edge geography on undirected graphs
The Complexity of Undirected Partizan Edge Geography
Data Structures and Algorithms
Summary
The paper looks at a two-player game played on a graph where players move tokens along edges and remove them after moving. Previously, it was known this game is very hard to solve on directed graphs, meaning figuring out who will win can take a lot of computational effort. The authors show that even when the graph is undirected, simple, and has limited connections, determining the winner remains equally hard. They also show this holds for a version of the game where players cannot share the same spot.
What this means in practice
- •For algorithm designers: Recognize that efficient algorithms for determining winners in partizan edge geography on undirected graphs are unlikely due to PSPACE-completeness.
- •For game developers: Use the PSPACE-completeness result to design puzzles or games involving graph token movement that guarantee computational challenge.
A theory result. No direct application yet.
Authors
Yuto Okada
Abstract
Partizan Edge Geography is a two-player game on a graph where each player has their own token on a vertex and moves their token to a neighbor in a turn removing the edge. Two player alternately move their tokens and the first player who cannot move loses the game. Fraenkel and Simonson (TCS, 1993) showed that the winner determination of this game is PSPACE-complete on directed graphs, given a graph and token positions. This paper resolves its complexity on undirected graphs by showing the PSPACE-completeness on bipartite undirected graphs of maximum degree 3. The same reduction also works for a variant where two tokens cannot be placed on the same vertex.