Overview
This research addresses the computational complexity of Partizan Edge Geography, a two-player game played on a graph. Specifically, it resolves the complexity of this game when played on undirected graphs. The study establishes that determining the winner for Partizan Edge Geography on undirected graphs is PSPACE-complete, even under specific graph conditions.
Research Context
Partizan Edge Geography involves two players, each with a token positioned on a vertex of a graph. Players alternately move their respective tokens to an adjacent vertex. A key rule of the game is that the edge traversed during a move is subsequently removed from the graph. The first player unable to execute a valid move, due to no available adjacent vertices via unremoved edges, loses the game.
Prior work by Fraenkel and Simonson (TCS, 1993) investigated the complexity of this game on directed graphs. Their findings indicated that the winner determination problem for Partizan Edge Geography is PSPACE-complete when played on directed graphs, given the graph structure and initial token positions.
Approach
The paper focuses on determining the complexity of Partizan Edge Geography when played on undirected graphs. The methodology employed a reduction technique. This approach aimed to demonstrate the equivalence of the game's winner determination problem to other known PSPACE-complete problems, thereby establishing its own complexity class.
Findings
The research establishes that the winner determination problem for Partizan Edge Geography on undirected graphs is PSPACE-complete. This complexity holds even under specific structural constraints of the graph: bipartite undirected graphs with a maximum degree of 3. The same reduction method used to prove this complexity for the standard game also applies to a specific variant. In this variant, an additional rule prevents the two player tokens from being simultaneously placed on the same vertex.
Why This Matters
The determination of PSPACE-completeness for Partizan Edge Geography on undirected graphs contributes to the understanding of computational complexity in game theory. This classification positions the game alongside other problems that are believed to be computationally intractable for efficient solution by algorithms, even under restrictive graph properties.