On the Complexity of the Mis ere Version of Three Games Played on Graphs

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