7
$\begingroup$

The directed Generalized Geography game is well-known to be PSPACE-complete, however, I could not find anything for the undirected version. I saw that in Hans L. Bodlaender, Complexity of path-forming games, Theoretical Computer Science, Volume 110, Issue 1, 15 March 1993, Pages 215-245 (thx to Marzio De Biasi for the link) it is posed as an open problem. Is it still open?

In fact, I wonder if there is a simple gadget that we can put in the place of every directed edge to make a straight-forward reduction from the directed version. Is it known that no such gadget can exist?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
10
$\begingroup$

Undirected (Vertex) Geography is in P. In particular, the game on graph $G$ with starting vertex $v$ is a win for player 1 if and only if every maximum matching of $G$ uses the vertex $v$. This can be checked in polynomial time.

The above is Theorem 1.1 from the paper "Undirected Edge Geography", by Fraenkel, Scheinerman and Ullman, Theoretical Computer Science 1993.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.