On the complexity of the misère version of three games played on graphs

DOI10.1016/J.TCS.2015.06.034MaRDI QIDQ2354773zbMATH OpenOpenAlexFDO

Authors Gabriel Renault, Simon Schmidt

Publication date 24 July 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.0400

zbMATH Keywords

combinatorial gamescomplexitygraphsmisère

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games involving graphs (91A43) Combinatorial games (91A46)

Abstract: We investigate the complexity of finding a winning strategy for the mis`ere version of three games played on graphs : two variants of the game $extNimG$, introduced by Stockmann in 2004 and the game $extVertexGeography$ on both directed and undirected graphs. We show that on general graphs those three games are $extPSPACE$-Hard or Complete. For one $extPSPACE$-Hard variant of $extNimG$, we find an algorithm to compute an effective winning strategy in time $mathcalO(sqrt|V(G)|.|E(G)|)$ when $G$ is a bipartite graph.

Recommendations

• A PSPACE-complete graph nim
• Vertex Nim played on graphs
• A Nim game played on graphs. II.
• On the computational complexities of various geography variants
• A Nim game played on graphs.

Cites work

• Complexity, appeal and challenges of combinatorial games
• Digraphs
• scientific article; zbMATH DE number 5145315 (Why is no real title available?)
• Undirected edge geography
• Vertex Nim played on graphs

Cited in

(10)

• Undirected edge geography
• A Nim game played on graphs.
• Pirates and treasure
• A PSPACE-complete graph nim
• Strings-and-coins and Nimstring are PSPACE-complete
• Vertex Nim played on graphs
• Graph convexity impartial games: complexity and winning strategies
• The combinatorial game \textsc{Nofil} played on Steiner triple systems
• Geography, Kotzig's Nim, and variants
• Misère annihilation games

This page was built for publication: On the complexity of the misère version of three games played on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2354773)