<p>The proof in my 1989 paper does not rely on the fact that the graph is undirected.</p>

<p>Directed treewidth is a different notion than the treewidth of the undirected graph obtained by changing each arc to an edge. </p>

CC BY-SA 3.0
2015-03-13T10:42:55.997Z
Well, I know that. My point is that with both notions the problem should remain PSPACE-complete.
user
CC BY-SA 3.0
2015-03-13T10:47:31.780Z
Welcome to CSTheory Hans !
R B
CC BY-SA 3.0
2015-03-13T10:08:45.920Z
2015-03-13T10:08:45.920Z
Hans Bodlaender
<p>So, in short, the question is, since QBF is PSPACE-complete for bounded pathwidth formulas, why isn't Geography PSPACE-complete for bounded pathwidth graphs?</p>

<p>I think the problem with this hardness argument is that the reduction from QBF to Geography by Schaefer does not preserve the pathwidth/treewidth of the formula. The reason is that, in Schaefer's construction, the variables must be added in the graph in the order in which they are quantified, NOT the order of the path decomposition. Hence, you cannot (in an obvious way) guarantee that the resulting digraph has small (undirected) treewidth.</p>

CC BY-SA 3.0
2015-03-13T10:55:36.067Z
2015-03-13T10:55:36.067Z
Michael Lampis
<p>Generalized Geography (GG) is played on a directed graph where a token is moved along arcs alternatively by two players. The vertices from which the token leaves are deleted. When a player cannot play anymore he loses (and his opponent wins).</p>

<p>GG is PSPACE-complete (see page 11, Figure 1 of "On the complexity of some two-person perfect-information games" of Schaefer) while its variant on undirected graphs is polynomial time solvable (see for instance <a href="http://www.math.cmu.edu/~af1p/Teaching/Combinatorics/F03/Class32.pdf" rel="nofollow noreferrer">here</a>). 
In the technical report <a href="http://www.cs.uu.nl/research/techreps/repo/CS-1989/1989-29.pdf" rel="nofollow noreferrer">Complexity of Path Forming Games</a> of Hans L. Bodlaender (1989), it is shown that GG becomes polynomial time solvable in graphs of bounded treewidth.</p>

<p>I have two questions concerning that result:<br>
1) Do you agree the algorithm is designed for undirected GG? (which is anyway in P for general graphs). Look at figure 4.1 for instance, plus the fact that the treewidth is not re-defined for directed graphs.<br>
2) As mentioned by Saeed in a related <a href="https://cstheory.stackexchange.com/questions/22445/for-which-families-of-graphs-is-generalized-geography-in-p/22463#22463">post</a>, "The problem is PSPACE-complete even on digraphs of directed tree width 1".<br>
Now, even if we consider (directed) GG, and the treewidth of the undirected graph obtained by changing each arc into an edge, it seems to be untrue that GG is easier with bounded treewidth: take any instance of QBF with bounded pathwidth (which remains PSPACE-complete, result of Atserias and Oliva), number the variables by their order of appearance in bags going from "left to right", and do the reduction of Schaefer (see also the link given by Saeed). The treewidth of the undirected version of the digraph produced by this reduction is bounded. No?</p>

<p>In view of 1) and 2) why do we think that bounded treewidth makes GG easier? </p>

CC BY-SA 3.0
2015-03-13T11:09:31.973Z
The underlying undirected graph has a big bipartite graph of degree at least 3 as a minor, and the tree width of that graph can be arbitrary large.
Saeed
<cc.complexity-theory><graph-algorithms><time-complexity>
Generalized Geography on graphs of bounded treewidth
user
# Generalized Geography on graphs of bounded treewidth

(Asked by: username_0 on 2015-03-13)

Generalized Geography (GG) is played on a directed graph where a token is moved along arcs alternatively by two players. The vertices from which the token leaves are deleted. When a player cannot play anymore he loses (and his opponent wins).

GG is PSPACE-complete (see page 11, Figure 1 of "On the complexity of some two-person perfect-information games" of Schaefer) while its variant on undirected graphs is polynomial time solvable (see for instance [here](http://www.math.cmu.edu/~af1p/Teaching/Combinatorics/F03/Class32.pdf)).
In the technical report [Complexity of Path Forming Games](http://www.cs.uu.nl/research/techreps/repo/CS-1989/1989-29.pdf) of Hans L. Bodlaender (1989), it is shown that GG becomes polynomial time solvable in graphs of bounded treewidth.

I have two questions concerning that result:  
1) Do you agree the algorithm is designed for undirected GG? (which is anyway in P for general graphs). Look at figure 4.1 for instance, plus the fact that the treewidth is not re-defined for directed graphs.  
2) As mentioned by username_1 in a related [post](https://cstheory.stackexchange.com/questions/22445/for-which-families-of-graphs-is-generalized-geography-in-p/22463#22463), "The problem is PSPACE-complete even on digraphs of directed tree width 1".  
Now, even if we consider (directed) GG, and the treewidth of the undirected graph obtained by changing each arc into an edge, it seems to be untrue that GG is easier with bounded treewidth: take any instance of QBF with bounded pathwidth (which remains PSPACE-complete, result of Atserias and Oliva), number the variables by their order of appearance in bags going from "left to right", and do the reduction of Schaefer (see also the link given by username_1). The treewidth of the undirected version of the digraph produced by this reduction is bounded. No?

In view of 1) and 2) why do we think that bounded treewidth makes GG easier?

**Tags:** cc.complexity-theory, graph-algorithms, time-complexity

> **Comments:**
> **username_1**: The underlying undirected graph has a big bipartite graph of degree at least 3 as a minor, and the tree width of that graph can be arbitrary large.  

---

## 2 answers

### Answer by username_4 on 2015-03-13. Score: 10 | Accepted answer

So, in short, the question is, since QBF is PSPACE-complete for bounded pathwidth formulas, why isn't Geography PSPACE-complete for bounded pathwidth graphs?

I think the problem with this hardness argument is that the reduction from QBF to Geography by Schaefer does not preserve the pathwidth/treewidth of the formula. The reason is that, in Schaefer's construction, the variables must be added in the graph in the order in which they are quantified, NOT the order of the path decomposition. Hence, you cannot (in an obvious way) guarantee that the resulting digraph has small (undirected) treewidth.


---

### Answer by username_2 on 2015-03-13. Score: 14

The proof in my 1989 paper does not rely on the fact that the graph is undirected.

Directed treewidth is a different notion than the treewidth of the undirected graph obtained by changing each arc to an edge.

> **Comments:**
> **username_0**: Well, I know that. My point is that with both notions the problem should remain PSPACE-complete.  
> **username_3**: Welcome to CSTheory Hans !  

---

