Metraipolis › archive › dc_b211615930ef
The Complexity of Undirected Partizan Edge Geography — arXiv:2609.18330
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.18330
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T16:13:18.266Z
- SHA-256 of the archived text
a518e383eb901cf55eafc9b35aa51cf3690333cd0c6ccc03559f483cf7630468- Stable URL of this page
https://metraipolis.com/documento/dc_b211615930ef
How to cite
The Complexity of Undirected Partizan Edge Geography — arXiv:2609.18330 — arXiv (en), https://arxiv.org/abs/2609.18330 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b211615930ef (Metraipolis archive dc_b211615930ef, sha256 a518e383eb901cf55eafc9b35aa51cf3690333cd0c6ccc03559f483cf7630468)
BibTeX
@misc{dcb211615930ef,
title = {The Complexity of Undirected Partizan Edge Geography — arXiv:2609.18330},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.18330},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b211615930ef; sha256 a518e383eb901cf55eafc9b35aa51cf3690333cd0c6ccc03559f483cf7630468},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.18330. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-17 in math.CO). Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Combinatorics (math.CO). Pagina del lavoro: https://arxiv.org/abs/2609.18330 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-15T15:38:58.289Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).