11
$\begingroup$

As @Marzio mentioned, the following game is known as 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.

$\endgroup$
  • 5
    $\begingroup$ The game is known as Generalized Geography and is PSPACE complete (even on planar directed graphs). See Complexity of Path Forming games for some variants (also some polynomial time variants) $\endgroup$ – Marzio De Biasi May 7 '14 at 14:29
  • $\begingroup$ Can you be more specific? E.g. from Marzio's link you can see that bounded treewidth is sufficient. $\endgroup$ – domotorp May 8 '14 at 10:01
  • 1
    $\begingroup$ @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. $\endgroup$ – Marzio De Biasi May 8 '14 at 11:47
8
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Saeed May 8 '14 at 22:35
  • 1
    $\begingroup$ @Saeed It seems that Umans and Lenhart solved the long standing open problem, see Hamiltonian Cycles in solid Grid Graphs. 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) $\endgroup$ – Marzio De Biasi May 8 '14 at 22:39
  • $\begingroup$ Thanks, that's really great and also it's not very new FOCS1997, but I've never seen it before! $\endgroup$ – Saeed May 8 '14 at 22:47
  • $\begingroup$ 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. $\endgroup$ – R B May 11 '14 at 11:03
  • $\begingroup$ 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? $\endgroup$ – domotorp Sep 27 '14 at 21:05
3
$\begingroup$

The problem is PSPACE-complete even on digraphs of directed tree width $1$. Just consider a PSPACE-Hardness construction provided in wiki. 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).

| cite | improve this answer | |
$\endgroup$

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.