# Generalized Geography on graphs of bounded treewidth

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). In the technical report Complexity of Path Forming Games 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 Saeed in a related post, "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 Saeed). 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?

• 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 Mar 13 '15 at 11:09