PreprintarXiv licencearXiv
The Complexity of Undirected Partizan Edge Geography
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.
Related
- A Winner Classification for Rooted Partizan Edge Geography on Heterogeneous Bouquets of Cycles
- Undirected edge geography games on stacked prism graphs
- Closure complexity of longest-edge bisection for triangular meshes
- Edge complexity of weighted graphs: involutory symmetries and NP-hardness
- Complexity, approximation, and extension of proper {a,b}-edge-weightings
BibTeX
@misc{okada2026complexity,
title = {{The Complexity of Undirected Partizan Edge Geography}},
author = {Yuto Okada},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.18330},
eprint = {2609.18330},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.18330},
}
RIS
TY - UNPB
TI - The Complexity of Undirected Partizan Edge Geography
AU - Yuto Okada
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2609.18330
UR - https://arxiv.org/abs/2609.18330
AB - 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.
ER -