The Complexity of Undirected Partizan Edge Geography
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.18330
curl -X POST /api/v1/records/arxiv/2609.18330/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.18330/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'