<p>The problem is PSPACE-complete even on digraphs of directed tree width $1$. Just consider a PSPACE-Hardness construction provided in <a href="http://en.wikipedia.org/wiki/Generalized_geography#Generalized_geography_is_PSPACE-hard" rel="nofollow">wiki</a>. If we delete a vertex $c$ from a graph, remaining graph is DAG. So we can decompose $G-c$ with width $0$. Then put $c$ in every bag (either guard bags or arborescence bags) of this decomposition. This results in decomposition of directed tree width $1$. (This is interesting because there are not many problems which are easy on DAGs and hard on bounded directed treewidth graphs).</p>

CC BY-SA 3.0
2014-05-08T12:26:40.640Z
2014-05-08T12:26:40.640Z
Saeed
<p>Generalized Geography (GG) is PSPACE-complete even on planar directed bipartite graphs,
but, as reported in:</p>

<p><a href="http://www.sciencedirect.com/science/article/pii/030439759390357Y/pdf?md5=f2e5b46744aa1e817cd19dc930b21c6e&amp;pid=1-s2.0-030439759390357Y-main.pdf" rel="nofollow">Hans L. Bodlaender, Complexity of path-forming games</a>, Theoretical Computer Science, Volume 110, Issue 1, 15 March 1993, Pages 215-245</p>

<p>GG (and some other PSPACE-complete variants) are linear-time-solvable in graphs of bounded treewidth.</p>

<p>SIDE NOTE: one of the Generalized Geography variants that has recently been proved to be PSPACE-complete is Tron (<em>Light Cycles</em> game): given an undirected graph, two players pick two different starting vertices, and then take turns, by moving to an adjacent vertex from their respective previous one in each step. The game ends when both players cannot move anymore. The player who traversed more vertices wins (it was conjectured to be PSPACE-complete in 1990 by Bodlaender and Kloks).<br>
<a href="http://arxiv.org/abs/1110.3211" rel="nofollow">Tillmann Miltzow, Tron, a combinatorial Game on abstract Graphs (2011)</a></p>

<p><br><strong>Edit</strong>: I made a small program to test the game on small $n \times m$ <em>rectangular solid grid graphs</em> (undirected), and the result suggests that it is polynomial time solvable also for this class of graphs (assuming that the first node picked by player A is the top-left node):</p>

<pre><code>               Width n
           1 2 3 4 5 6 7 8 
         1 A B A B A B A B    Winning matrix up to 8x8
         2   B B B B B B B 
         3     A B A B A B 
Height m 4       B B B B B  
         5         A B A B 
         6           B B B 
         7             A B 
         8               B 
</code></pre>

<p>Curiously, the same matrix is obtained if player A can choose an arbitrary starting node. </p>

<p>As said in the comments, I think that the complexity of deciding if there is a winning strategy when GG is played on <em>solid grid graphs</em> (with arbitrary shapes, but without holes) is not known and probably it is not so easy to prove something about it (indeed the - somewhat related - problem of deciding if a solid grid graph has an Hamiltonian <em>path</em> is still open, though deciding if a solid grid graph has an Hamiltonian <em>cycle</em> is polynomial time solvable).</p>

<p>A final trivial note: GG is polynomial time solvable also in complete graphs.</p>

CC BY-SA 3.0
2014-05-08T22:35:18.313Z
Are you sure hamiltonian cycle in solid grid graph is polynomial time solvable? As I can remember it's just unknown, on the other hand if that solid grid has some structures (like L shape, T shape, mxn, ...) it's polynomial time solvable, but I cannot remember any paper which solves it in polynomial time in general solid grid graphs. Do you have a reference?
Saeed
CC BY-SA 3.0
2014-05-08T22:39:25.197Z
@Saeed It seems that Umans and Lenhart solved the long standing open problem, see [Hamiltonian Cycles in solid Grid Graphs](http://users.cms.caltech.edu/~umans/papers/LU97.ps). A few time ago I searched for recent/related results about Hamiltonian path on solid grid graphs, but found nothing. (I think there is also a related question on cstheory somewhere)
Marzio De Biasi
CC BY-SA 3.0
2014-05-08T22:47:01.743Z
Thanks, that's really great and also it's not very new [FOCS1997](http://dl.acm.org/citation.cfm?id=796334), but I've never seen it before!
Saeed
CC BY-SA 3.0
2014-05-11T11:03:03.260Z
Great answer @MarzioDeBiasi. Actually I came across this problem in a different setting, which can be modeled as a grid graph, but was curious about its generalization as well.
R B
CC BY-SA 3.0
2014-09-27T21:05:03.547Z
I've spent half an hour but could not find any references for Undirected Generalized Geography. I'm sure it must have been shown by someone to be PSPACE-complete. Do you maybe know about it?
domotorp
CC BY-SA 3.0
2014-09-30T06:45:21.777Z
@domotorp: sorry, I saw the comment after you posted the question about it (and Michael already gave you the correct reference :-)
Marzio De Biasi
CC BY-SA 3.0
2014-09-30T08:22:14.007Z
np, in fact, after seeing the paper, I've remembered that I've heard this proof already...
domotorp
CC BY-SA 3.0
2014-05-08T09:36:31.730Z
2014-05-11T21:51:22.777Z
2014-05-11T21:51:22.777Z
Marzio De Biasi
<p>As @Marzio mentioned, the following game is known as <a href="http://en.wikipedia.org/wiki/Generalized_geography">Generalized Geography</a>.</p>

<p>Given a graph $G=(V,E)$ and a starting vertex $v \in V$, the game is defined as follows:</p>

<p>At each turn (two players alternating), a player chooses $u\in N(v)$, and then the following happens:</p>

<ol>
<li>$v$, as well as all of its edges, is removed from $G$.</li>
<li>$u\to v$ (i.e. $v$ is updated to be the vertex $u$).</li>
</ol>

<p>The player who is forced to select a "dead end" (i.e. a vertex with no outgoing edges) loses.</p>

<p><strong>In which graph families is the optimal strategy computable in polynomial time?</strong></p>

<p>For example, it's easy to see that if $G$ is a DAG, then we can easily compute the optimal strategy for the players.</p>

CC BY-SA 3.0
2014-05-07T14:29:18.993Z
The game is known as [Generalized Geography](http://en.wikipedia.org/wiki/Generalized_geography) and is PSPACE complete (even on planar directed graphs). See  [Complexity of Path Forming games](http://www.cs.uu.nl/research/techreps/repo/CS-1989/1989-29.pdf) for some variants (also some polynomial time variants)
Marzio De Biasi
CC BY-SA 3.0
2014-05-08T10:01:32.513Z
Can you be more specific? E.g. from Marzio's link you can see that bounded treewidth is sufficient.
domotorp
CC BY-SA 3.0
2014-05-08T11:47:44.913Z
@domotorp: I think that GG on *undirected solid grid graphs* is an unsolved open problem (perhaps also not studied). I'll google a little bit to see if it is a new problem. Whilst, in the case of directed solid grid graphs it seems easy to simulate "holes" using the directed edges, so it should be PSPACE-complete.
Marzio De Biasi
<graph-theory><graph-algorithms><gt.game-theory>
For which families of graphs is Generalized Geography in $P$?
R B
# For which families of graphs is Generalized Geography in $P$?

(Asked by: username_0 on 2014-05-07)

As @Marzio mentioned, the following game is known as [Generalized Geography](http://en.wikipedia.org/wiki/Generalized_geography).

Given a graph $G=(V,E)$ and a starting vertex $v \in V$, the game is defined as follows:

At each turn (two players alternating), a player chooses $u\in N(v)$, and then the following happens:

1. $v$, as well as all of its edges, is removed from $G$.
2. $u\to v$ (i.e. $v$ is updated to be the vertex $u$).

The player who is forced to select a "dead end" (i.e. a vertex with no outgoing edges) loses.

**In which graph families is the optimal strategy computable in polynomial time?**

For example, it's easy to see that if $G$ is a DAG, then we can easily compute the optimal strategy for the players.

**Tags:** graph-theory, graph-algorithms, gt.game-theory

> **Comments:**
> **username_1**: The game is known as [Generalized Geography](http://en.wikipedia.org/wiki/Generalized_geography) and is PSPACE complete (even on planar directed graphs). See  [Complexity of Path Forming games](http://www.cs.uu.nl/research/techreps/repo/CS-1989/1989-29.pdf) for some variants (also some polynomial time variants)  
> **username_2**: Can you be more specific? E.g. from Marzio's link you can see that bounded treewidth is sufficient.  
> **username_1**: @username_2: I think that GG on *undirected solid grid graphs* is an unsolved open problem (perhaps also not studied). I'll google a little bit to see if it is a new problem. Whilst, in the case of directed solid grid graphs it seems easy to simulate "holes" using the directed edges, so it should be PSPACE-complete.  

---

## 2 answers

### Answer by username_1 on 2014-05-08. Score: 8 | Accepted answer

Generalized Geography (GG) is PSPACE-complete even on planar directed bipartite graphs,
but, as reported in:
Hans L. Bodlaender, Complexity of path-forming games, Theoretical Computer Science, Volume 110, Issue 1, 15 March 1993, Pages 215-245
GG (and some other PSPACE-complete variants) are linear-time-solvable in graphs of bounded treewidth.
SIDE NOTE: one of the Generalized Geography variants that has recently been proved to be PSPACE-complete is Tron (Light Cycles game): given an undirected graph, two players pick two different starting vertices, and then take turns, by moving to an adjacent vertex from their respective previous one in each step. The game ends when both players cannot move anymore. The player who traversed more vertices wins (it was conjectured to be PSPACE-complete in 1990 by Bodlaender and Kloks).
Tillmann Miltzow, Tron, a combinatorial Game on abstract Graphs (2011)
Edit: I made a small program to test the game on small $n \times m$ rectangular solid grid graphs (undirected), and the result suggests that it is polynomial time solvable also for this class of graphs (assuming that the first node picked by player A is the top-left node):
               Width n
           1 2 3 4 5 6 7 8 
         1 A B A B A B A B    Winning matrix up to 8x8
         2   B B B B B B B 
         3     A B A B A B 
Height m 4       B B B B B  
         5         A B A B 
         6           B B B 
         7             A B 
         8               B 

Curiously, the same matrix is obtained if player A can choose an arbitrary starting node. 
As said in the comments, I think that the complexity of deciding if there is a winning strategy when GG is played on solid grid graphs (with arbitrary shapes, but without holes) is not known and probably it is not so easy to prove something about it (indeed the - somewhat related - problem of deciding if a solid grid graph has an Hamiltonian path is still open, though deciding if a solid grid graph has an Hamiltonian cycle is polynomial time solvable).
A final trivial note: GG is polynomial time solvable also in complete graphs.

> **Comments:**
> **username_3**: Are you sure hamiltonian cycle in solid grid graph is polynomial time solvable? As I can remember it's just unknown, on the other hand if that solid grid has some structures (like L shape, T shape, mxn, ...) it's polynomial time solvable, but I cannot remember any paper which solves it in polynomial time in general solid grid graphs. Do you have a reference?  
> **username_1**: @username_3 It seems that Umans and Lenhart solved the long standing open problem, see [Hamiltonian Cycles in solid Grid Graphs](http://users.cms.caltech.edu/~umans/papers/LU97.ps). A few time ago I searched for recent/related results about Hamiltonian path on solid grid graphs, but found nothing. (I think there is also a related question on cstheory somewhere)  
> **username_3**: Thanks, that's really great and also it's not very new [FOCS1997](http://dl.acm.org/citation.cfm?id=796334), but I've never seen it before!  
> **username_0**: Great answer @MarzioDeBiasi. Actually I came across this problem in a different setting, which can be modeled as a grid graph, but was curious about its generalization as well.  
> **username_2**: I've spent half an hour but could not find any references for Undirected Generalized Geography. I'm sure it must have been shown by someone to be PSPACE-complete. Do you maybe know about it?  
> **username_1**: @username_2: sorry, I saw the comment after you posted the question about it (and Michael already gave you the correct reference :-)  
> **username_2**: np, in fact, after seeing the paper, I've remembered that I've heard this proof already...  

---

### Answer by username_3 on 2014-05-08. Score: 3

The problem is PSPACE-complete even on digraphs of directed tree width $1$. Just consider a PSPACE-Hardness construction provided in [wiki](http://en.wikipedia.org/wiki/Generalized_geography#Generalized_geography_is_PSPACE-hard). If we delete a vertex $c$ from a graph, remaining graph is DAG. So we can decompose $G-c$ with width $0$. Then put $c$ in every bag (either guard bags or arborescence bags) of this decomposition. This results in decomposition of directed tree width $1$. (This is interesting because there are not many problems which are easy on DAGs and hard on bounded directed treewidth graphs).


---

