4
$\begingroup$

A post here For which families of graphs is Generalized Geography in $P$? mentioned that generalized geography on solid grid graphs is open. Is the question still open? A quick search on Google shows no results, but I wanted to see if anyone with more familiarity with the area can confirm.

Related to this question, I also wonder if Generalized Geography on grid graphs with holes or thin graphs are also open? What about on bipartite graphs, expander graphs...etc?

$\endgroup$
  • 2
    $\begingroup$ Up to my knowkledge: (vertex) GG on undirected graphs is in P (see this Q&A and this paper) so it is in P also for grid graphs. For directed bipartite graphs it remains PSPACE-complete. For directed solid grid graphs, I think there is an easy way to simulate a planar directed graph, and prove that it is PSPACE-complete (but I didn't find it in any paper). $\endgroup$ – Marzio De Biasi Mar 2 '15 at 8:16
  • $\begingroup$ Is there a reference for directed bipartite graphs? $\endgroup$ – Quanquan Liu Mar 2 '15 at 22:45
0
$\begingroup$

Just to complete my comment:

GG remains PSPACE-complete on planar bipartite directed graphs with maximum degree 3 (see
D. Lichtenstein, M. Sipser: GO Is Polynomial-Space Hard. J. ACM 27(2): 393-401 (1980) )

But (vertex) GG on undirected graphs is in P (see this Q&A and this paper) so it is in P also for grid graphs.

For directed solid grid graphs I didn't find any reference, however, I think there is an easy way to simulate a planar bipartite directed graph; the following idea should work:

enter image description here
Both the "diamond" structure (A) and the crossover gadget (C), can be converted into an equivalent (directed) solid grid graph gadget (B) and (D).

$\endgroup$
  • $\begingroup$ Ah cool. The reduction looks good to me. Nice use of the edges of the grey vertices to prevent a yellow vertex from ever being able to use them. $\endgroup$ – Quanquan Liu Mar 2 '15 at 23:34
  • $\begingroup$ One thing to be careful about is the parity of the grid graph edges. If you're using more than one grid graph edge for each planar graph edge (the number of grid graph edges used to represent a single planar graph edge should be odd). $\endgroup$ – Quanquan Liu Mar 2 '15 at 23:40
  • $\begingroup$ @q2liu: yes. The source graph is bipartite, so parity should not be an issue. In the graph (B) I "compacted" the diamonds: 1 blue edge -> 3 edges, 1 red edge -> 1 red edge; graph (D) is also "compacted". $\endgroup$ – Marzio De Biasi Mar 3 '15 at 9:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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