7
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Saeed
    Mar 13, 2015 at 11:09

2 Answers 2

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
0
14
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Well, I know that. My point is that with both notions the problem should remain PSPACE-complete. $\endgroup$
    – user
    Mar 13, 2015 at 10:42
  • 6
    $\begingroup$ Welcome to CSTheory Hans ! $\endgroup$
    – R B
    Mar 13, 2015 at 10:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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