<p>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.</p>

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

CC BY-SA 3.0
2014-09-28T22:11:50.423Z
2014-09-28T22:11:50.423Z
Michael Lampis
<p>The directed <a href="http://en.wikipedia.org/wiki/Generalized_geography">Generalized Geography</a> game is well-known to be PSPACE-complete, however, I could not find anything for the undirected version. I saw that in <a href="http://www.sciencedirect.com/science/article/pii/030439759390357Y/pdf?md5=f2e5b46744aa1e817cd19dc930b21c6e&amp;pid=1-s2.0-030439759390357Y-main.pdf">Hans L. Bodlaender, Complexity of path-forming games, Theoretical Computer Science, Volume 110, Issue 1, 15 March 1993, Pages 215-245</a> (thx to Marzio De Biasi for the link) it is posed as an open problem. Is it still open?</p>

<p>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?</p>

<graph-theory><pspace><combinatorial-game-theory><two-player-games>
Is there a gadget that reduces generalized geography to undirected graphs?
domotorp
# Is there a gadget that reduces generalized geography to undirected graphs?

(Asked by: username_0 on 2014-09-28)

The directed [Generalized Geography](http://en.wikipedia.org/wiki/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](http://www.sciencedirect.com/science/article/pii/030439759390357Y/pdf?md5=f2e5b46744aa1e817cd19dc930b21c6e&pid=1-s2.0-030439759390357Y-main.pdf) (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?

**Tags:** graph-theory, pspace, combinatorial-game-theory, two-player-games


---

## 1 answers

### Answer by username_1 on 2014-09-28. Score: 10 | Accepted answer

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.


---

