# Complexity of games with graph classes

Let $$\mathfrak{G}$$ be the class of all finite directed and undirected graphs. Let $$A,B\subseteq \mathfrak{G}$$, $$A$$ and $$B$$ are closed under graph isomorphisms, and $$A \cap B = \varnothing$$. Consider the following two player game. On the graph $$G \in \mathfrak{G}$$ with the starting vertex $$u$$, play as follows: the first player presents $$x_1 \subseteq V(G)$$ such that $$\forall v\in x_1\; uv\in E(G)$$. Then the players in turn present the sets of vertices, so that for any different $$x_i$$ and $$x_j$$ satisfy $$x_i \cap x_j = \varnothing$$, and $$\forall v\in x_k \; \exists w\in x_{k-1} : wv\in E(G)$$. Conditions for victory and defeat (checked on each turn in the order of the following list):

1. If on turn $$n$$ there exists $$k$$ such that the induced subgraph $$\bigcup_\limits{i=k}^n x_i$$ contains a subgraph $$H$$ isomorphic to a graph from $$A$$, then the player who made the move $$n$$ wins.
2. If on turn $$n$$ there exists $$k$$ such that the induced subgraph $$\bigcup_\limits{i=k}^n x_i$$ contains a subgraph $$H$$ isomorphic to a graph from $$B$$, then the player who made the move $$n$$ loses.
3. If after some move the player cannot make a move, then he loses.

For example, if condition 2 is satisfied on the last move, then the player who made this move loses, because condition 2 is checked earlier than condition 3. Or if after the player's move a graph appears containing subgraphs from both $$A$$ and $$B$$, then he wins, because condition 1 is checked before condition 2. Let call this game $$A-B$$ game. Consider the following language: $$A-B-NG:=\{(G,u): \text{there is a winning strategy for the first player in A-B game} \}$$ The complexity of this language depends on the classes we are considering. For example, if $$pt$$ is one-vertex graph, then $$\{pt\}-B-NG \in \mathrm{DTIME(1)}$$, because condition 1 is satisfied for all non-empty graphs. But $$GG\leq_p \varnothing - \varnothing - NG$$, therefore $$\varnothing - \varnothing - NG \in \mathrm{PSPACE-complete}$$ (because $$\varnothing - \varnothing - NG \leq_p GG$$ ). Is it possible to choose $$A$$,$$B$$ so that $$A-B-NG$$ will have an even worse nesting, that is, it will lie in a class strictly above $$\mathrm{PSPACE}$$, or containing $$\mathrm{PSPACE}$$ ?

• Are $A$ and $B$ just a finite collection of graphs? If not, how are they presented? I don't see how to reduce Generalized Geography to your game, as you allow players to pick sets of vertices rather than a single vertex. Oct 15, 2021 at 15:31
• I think we should accept that the Turing machine has an oracle for both sets. You are absolutely right, I have not indicated the correct reduction from $GG$ to $\varnothing - \varnothing- NG$ :(. I assume that it exists and I will think about how to build it. Oct 15, 2021 at 18:40

No, it is not possible to go above PSPACE, because all positional games with an exponentially large game tree are in PSPACE; you can just check all the options. And the game when $$A=B=\emptyset$$ is indeed PSPACE-hard, I've found a gadget to reduce the original Generalized Geography to it.
• You just need to store which vertices have been claimed, plus the last claimed vertex set. This is $3^n$ bits. Oct 15, 2021 at 20:34