# On the Computational Complexities of Various Geography Variants

Nathan Fox111Mathematics and Statistics, Canisius College, Buffalo, New York,
<EMAIL_ADDRESS>Carson Geissler222The College of Wooster, Wooster, Ohio,
<EMAIL_ADDRESS>
###### Abstract

Generalized Geography is a combinatorial game played on a directed graph.
Players take turns moving a token from vertex to vertex, deleting a vertex
after moving the token away from it. A player unable to move loses. It is well
known that the computational complexity of determining which player should win
from a given position of Generalized Geography is pspace-complete. We
introduce several rule variants to Generalized Geography, and we explore the
computational complexity of determining the winner of positions of many
resulting games. Among our results is a proof that determining the winner of a
game known in the literature as Undirected Partizan Geography is pspace-
complete, even when restricted to being played on a bipartite graph.

##  1 Introduction

The underpinning for our work is the game of Generalized Geography, also known
as Generalized Vertex Geography, and, henceforth in this paper, simply as
geography. geography is played on a directed graph $G$, with a token that
begins on some vertex $v$ of $G$. Players take turns moving the token along
arcs of $G$. After a player moves the token, that player deletes the vertex
the token moved from, so that no later move can visit that vertex. A player
unable to move loses. The name “Geography” comes from the children’s game of
the same name in which players take turns naming cities. Cities cannot repeat,
and the first letter in each city’s name must be the same as the last letter
of the previous city’s name. The cities correspond to vertices in $G$, the
letter matching restriction to arcs in $G$, and the “no repeats” rule to the
vertex deletion rule.

As described, geography is an impartial combinatorial game with the normal
play convention. Combinatorial games are finite games of perfect information
played with two players. Under normal play, a player loses when unable to
move. Finally, in an impartial game, the same set of moves is available in a
given position regardless of which player’s turn it is. In geography, this
amounts to the fact that there is a single token that players take turns
moving. This is as opposed to partizan games, like chess, in which each player
has their own set of moves available to them in a given position [winways].

A natural question to ask about combinatorial games is, given a position,
which player should win assuming both players play optimally? For some games,
such as Nim, it is straightforward to decide which player wins [nim]. For
other games, such as chess, it is far less clear [chess]. Computational
complexity is a formal lens through which we can quantify the difficulty of
determining which player should win. For brevity, we henceforth refer to this
question simply as the _complexity of the game_. A classical result states
that geography is pspace-complete [geogreduct]. On the other hand, since there
is a polynomial time algorithm to determine the winner of Nim, Nim is in p. No
problem in p is pspace-complete unless p=pspace, a unsolved proposition
stronger than p=np that is generally expected to be false.

There is a long tradition of studying the complexities of variants of
geography [fsugeog, fsgeog, monti2018variants, bodlaender1993complexity,
darmann2014shortest, schaefergeog]. In this paper, we examine four ways of
modifying geography, which can be combined to yield a multitude of geography
variants. Our motivation comes from the board game Santorini [santorini]; our
variants adjust the rules of geography to become more like Santorini. Here are
the variations we consider:

Directed versus Undirected:

geography is played on a directed graph, but it can just as easily be played
on an undirected graph.

Impartial versus Partizan:

As mentioned before, geography is an impartial game. The game can be made
partizan by replacing the single token with two tokens, one controlled by each
player, with the additional rule that the tokens cannot occupy the same vertex
simultaneously [fsgeog]. We refer to geography with only this alteration as
partizan geography.

Restricted versus Free Deletion:

In geography, a move consists of moving a token from a vertex to a successive
vertex and then deleting the vertex moved from. In this paper, we refer to
this rule as _restricted deletion_. We contrast this with a different move
rule, which we call _free deletion_. Under free deletion, a move consists of
moving a token from a vertex to a successive vertex and then deleting a vertex
that could have been moved from. In the undirected case, this amounts to
deleting any neighbor of the vertex moved to; in the directed case it amounts
to deleting any predecessor of the vertex being moved to.

Stacked Vertices:

In this variant, each vertex has a positive integer height associated to it.
When a vertex would be deleted, instead its height is decreased by $1$. If the
height of a vertex becomes $0$, it is deleted. In all cases, we treat the
maximum allowed height as a fixed parameter, thereby still guaranteeing that
the length of the game is polynomial in the number of vertices in the graph
(Proposition 1).

Without introducing any additional modifications, stacked vertices cannot
actually change the complexity of a game, because a game with stacked vertices
would be equivalent to a game without stacked vertices where a vertex of
height $k$ is replaced by $k$ vertices (analogously to the proof of
Proposition 4). So, along with the setup of stacked vertices comes a moving
restriction: From a vertex of height $k$, a move is only legal to a successive
vertex of height at least $k-1$. Note that this move restriction only becomes
relevant for maximum heights of $3$ or greater; any game with maximum height
$2$ is equivalent to a game with maximum height $1$ (Proposition 4).

Our notation for a game consists of three letters and a numerical subscript.
The first letter, d or u, stands for directed or undirected. The second
letter, i or p, stands for impartial or partizan. The third letter, r or f,
stands for restricted or free deletion. Finally, a numerical subscript denotes
the maximum allowed height of a stacked vertex. A maximum height of $1$ is
equivalent to not allowing stacked vertices, so we may omit the subscript when
it would be $1$. Under this notation, geography is denoted dir or
$\text{{dir}}_{1}$.

Table 1 contains a summary of known results and our results. Of particular
note are all of the games with restricted deletion and no stacking, as all
have been considered previously. The game uir, known in the source studying it
as undirected vertex geography, has a straightforward solution [fsugeog],
which extends to the stacked game $\text{{uir}}_{2}$. That same source
mentions the game upr near the end, stating only that it is np-hard. We prove
in Section 4.1 that it is, in fact, pspace-complete. The game of partizan
geography (dpr) is known to be pspace-complete, even when restricted to
bipartite graphs with maximum in/out degree at most two and maximum total
degree at most three [fsgeog]. The game of geography (dir) is also still
pspace-complete under such restrictions. It remains pspace-complete if the
graph is additionally required to be planar [geogreduct].

The proofs in this paper are organized with the non-stacking pspace reductions
first (Theorems 1 through 4), starting with the simplest reduction. Then, we
prove Theorem 5 about the game uif, and we conclude with Theorem 6 about
$\text{{uir}}_{4}$.

Game | Complexity | Analysis
---|---|---
dir |  pspace-complete, even for bipartite with degree $\leq 3$ | [schaefergeog, geogreduct]
dif |  pspace-complete, even for bipartite graphs | Section 3.1
dpr |  pspace-complete, even for bipartite with degree $\leq 3$ | [fsgeog]
dpf |  pspace-complete, even for bipartite graphs | Section 3.2
$\text{{uir}}_{2}$ | In p | [fsugeog]
$\text{{uir}}_{4}$ |  pspace-complete, even for bipartite with degree $\leq 3$ | Section 6
$\text{{uif}}_{2}$ | In p for bipartite graphs | Section 5
upr |  pspace-complete, even for bipartite graphs | Section 4.1
upf |  pspace-complete | Section 4.2
Table 1: Summary of computational complexities of geography variants

##  2 Preliminaries

###  2.1 Notation and Conventions

When we refer to a _game_ , we refer to all possible instances or positions of
that game. All of our games have two players, whom we conventionally name Left
and Right. In our proofs, we use the pronouns _she_ for Left and _he_ for
Right to help distinguish between the players. In a particular position,
either player might be the active player, though, following convention,
positions we construct always have Left as the active player, if possible.
Furthermore, if a game is impartial, a position is called an N-position if the
next player to move should win and a P-position otherwise.

Sometimes, we want to refer to multiple games at once. In place of d or u, we
write x when it can be either. Similarly, we can write y in place of i or p
and z in place of r or f. The game $\text{{xyz}}_{k}$ has an underlying graph
$G$ that could either be directed or undirected. If $G$ is undirected, given
vertices $v$ and $w$ in $G$, we write $v\sim w$ if $v$ and $w$ are adjacent.
If $G$ is directed, given vertices $v$ and $w$ in $G$, we write $v\to w$ if
there is an arc from $v$ to $w$. In this case, we say that $w$ _succeeds_ $v$
and that $v$ _precedes_ $w$. A move in $\text{{xyz}}_{k}$ consists of the
active player moving a token from some vertex $v$ to another vertex $w$ and
then reducing the height of a vertex $u$ by $1$ (and deleting $u$ if its
height reaches $0$). For convenience of notation, we encode such a move as
$\left(v,w,u\right)$. If $u=v$ (as must be the case under restricted
deletion), we say that the move is _regular_ ; otherwise it is _irregular_.

This paper includes several diagrams of positions. Vertices of graphs are
denoted by circles which may contain symbols. The symbol $T$ denotes the token
in an impartial game; the symbols $L$ and $R$ denote Left’s and Right’s tokens
in a partizan game. A number inside a circle denotes the height of a vertex in
a game with stacking. Other symbols in a circle have no meaning within the
game and are present only to clarify the diagram. See Figure 1 on page 1 for
an example of partizan positions with and without stacking, and see Figure 4
on page 4 for an example of an impartial position without stacking.

In this paper, we are concerned with the computational complexity of a given
game. All of the games $\text{{xyz}}_{k}$ are in pspace (Proposition 1), so
proving pspace-completeness amounts only to proving pspace-hardness. We are
interested in separating games that are in p from games that are pspace-
complete, so we employ polynomial-time reductions [karp]. We use Karp’s
notation $K_{1}\leq_{p}K_{2}$ to mean that game $K_{1}$ is polynomial-time-
reducible to game $K_{2}$, which means that the complexity of $K_{2}$ is at
least that of $K_{1}$. Several of the proofs in this paper proceed via
reductions. All of our reductions take place in polynomial time, because in
each case a position is being transformed into another position, the latter of
which has size polynomial in the size of the former, and where each step of
the transformation can be performed in polynomial time.

###  2.2 Quantified Boolean Formulas

In order to prove that games are pspace-complete, we need a pspace-complete
problem to start reductions from. The classical choice is the decision problem
tqbf, sometimes known as qsat, which asks whether a given quantified boolean
formula is true. Without loss of generality, we can always assume that the
expression is given in the form $\exists x_{1}\forall x_{2}\exists
x_{3}\cdots\exists x_{n-1}\forall x_{n}P(x_{1},x_{2},\ldots,x_{n})$ for some
predicate $P$. This problem is still pspace-complete if we require $P$ to be a
3-CNF formula (conjunctive normal form with exactly three literals per clause)
[gareyjohnson]. For example, we might consider an expression such as $\exists
x_{1}\forall x_{2}\exists x_{3}\forall x_{4}\left(x_{1}\vee\bar{x}_{2}\vee
x_{3}\right)\wedge\left(x_{1}\vee\bar{x}_{3}\vee\bar{x}_{4}\right)$.
Conventionally, we use $n$ to refer to the number of variables (always even)
and $m$ to refer to the number of clauses. Henceforth in this paper, the term
tqbf assumes this normal form with all mentioned restrictions in place.

Note the distinction between _variable_ and _literal_. A variable is one of
the symbols $x_{i}$; a literal is a variable or its negation. We occasionally
say that a literal _contains_ a variable.

tqbf can be formulated as a game as follows. Two players, Left and Right, are
given a 3-CNF formula $P\left(x_{1},x_{2},\ldots,x_{n}\right)$. The players,
starting with Left, take turns setting the truth values of the variables in
increasing order of the index. (Left starts by setting $x_{1}$, then Right
sets $x_{2}$, etc.) Once all variables have been assigned truth values, Left
wins if $P\left(x_{1},x_{2},\ldots,x_{n}\right)$ is true, and Right wins if it
is false. Deciding who wins this game is precisely the same as deciding the
truth value of $\exists x_{1}\forall x_{2}\exists x_{3}\cdots\exists
x_{n-1}\forall x_{n}P(x_{1},x_{2},\ldots,x_{n})$.

###  2.3 Simple Propositions

The following results provide some basic relationships between our games and a
foundation for the more substantial results to follow in later sections.

######  Proposition 1.

The game $\text{{xyz}}_{k}$ is in pspace.

###### Proof.

To represent a position in $\text{{xyz}}_{k}$, we need to encode the
underlying graph $G$, the height of each vertex, the locations and owners of
all tokens, and which player is to move. If $G$ has $n$ vertices, it can be
encoded using $O(n^{2})$ bits by listing its vertices and its arcs/edges.
Since we treat $k$ as a constant, $O(n)$ bits are required to encode the
heights of all of the vertices. Then, since each of our variants uses at most
two tokens, the remainder of the information can be encoded using $O(\log n)$
bits, identifying by a numerical index each vertex with a token. Hence, a
position with $n$ vertices can be encoded using $O(n^{2})$ bits, a polynomial
in $n$.

We must now show that the winner can be determined using space polynomial in
$n$. Every move of the game must reduce the height of a vertex, so the total
number of moves in the game is at most the total height of all of the
vertices. This, in turn, is at most $nk$, as each vertex can have height at
most $k$. So, we can explore the entire game tree with backtracking, needing
to store at most $O(n)$ positions in memory simultaneously. Each position can
be stored using $O(n^{2})$ bits, so we need to store at most $O(n^{3})$ bits
of game information. To track the winner in each position, we need only an
additional bit per position, so we can determine the winner using $O(n^{3})$
space, a polynomial in $n$, as required. ∎

######  Proposition 2.

If $k<\ell$, the game $\text{{xyz}}_{k}$ is no more complex than
$\text{{xyz}}_{\ell}$, even if the same restriction is placed on the
underlying graphs for both.

###### Proof.

If $k<\ell$, any instance of $\text{{xyz}}_{k}$ is also an instance of
$\text{{xyz}}_{\ell}$ with the same underlying graph. ∎

######  Proposition 3.

The game $\text{{uyz}}_{k}$ is no more complex than $\text{{dyz}}_{k}$.

###### Proof.

To convert an instance of $\text{{uyz}}_{k}$ to an equivalent instance of
$\text{{dyz}}_{k}$, replace each edge with a pair of arcs, one going each
direction. ∎

######  Proposition 4.

The complexities of the games $\text{{xyz}}_{1}$ and $\text{{xyz}}_{2}$ are
the same, and they are still the same (as each other) when restricted to
bipartite graphs.

###### Proof.

By Proposition 2, $\text{{xyz}}_{2}$ is no less complex than
$\text{{xyz}}_{1}$. We now give a polynomial-time reduction from
$\text{{xyz}}_{2}$ to $\text{{xyz}}_{1}$, thereby also showing that
$\text{{xyz}}_{2}$ is no more complex than $\text{{xyz}}_{1}$. Additionally,
under our reduction the underlying graph in one instance is bipartite if and
only if the other is. Given an instance $K$ of $\text{{xyz}}_{2}$ on a graph
$G$, create an instance $T(K)$ of $\text{{xyz}}_{1}$ with underlying graph
$G^{\prime}$ as follows:

  * •

For a vertex $v\in G$, $G^{\prime}$ has a vertex $v_{1}$ if $v$ has height $1$
in $K$, and $G^{\prime}$ has vertices $v_{1}$ and $v_{2}$ if $v$ has height
$2$ in $K$.

  * •

If $G$ is undirected, if $v\sim w$ in $G$, then $v_{1}\sim w_{1}$ in
$G^{\prime}$. Furthermore, $v_{1}\sim w_{2}$, $v_{2}\sim w_{1}$, and
$v_{2}\sim w_{2}$ whenever both vertices involved exist. Analogously, if $G$
is directed, if $v\to w$ in $G$, then $v_{1}\to w_{1}$ in $G^{\prime}$.
Furthermore, $v_{1}\to w_{2}$, $v_{2}\to w_{1}$, and $v_{2}\to w_{2}$ whenever
both vertices involved exist.

  * •

If vertex $v$ of height $1$ has a token on it in $K$, then $v_{1}$ has that
token on it in $T(K)$.

  * •

If vertex $v$ of height $2$ has a token on it in $K$, then $v_{2}$ has that
token on it in $T(K)$.

See Figure 1 for an example of this transformation. This example is directed
and partizan, but an analogous transformation works if the game is undirected
and/or impartial.

$2$$2L$$1$$1R$$2$

$\Downarrow$

$R$$L$

Figure 1: Reduction from $\text{{dpz}}_{2}$ to $\text{{dpz}}_{1}$.

We claim that Left wins $T(K)$ if and only if she wins $K$. We argue by
induction on the total height of all vertices in $K$. As a base case, note
that if all vertices in $K$ have height $1$, then $K=T(K)$ (aside from vertex
subscripts in $T(K)$), so they have the same winner. Now, suppose all games
$\bar{K}$ with smaller total height than $K$ have the property that the same
player wins $\bar{K}$ and $T(\bar{K})$. Now, consider an optimal move
$\left(v,w,u\right)$ for the active player in $K$. Denote by $K_{1}$ the
resulting instance of $\text{{xyz}}_{2}$. In $T(K)$, any move of the form
$\left(v_{i},w_{j},u_{\ell}\right)$ is legal, provided all vertices exist and
$i$ is as large as possible (so that there is actually a token there to be
moved). Choose the move where $i$, $j$, and $\ell$ are all as large as
possible. The result is an instance $K_{1}^{\prime}$ of $\text{{xyz}}_{1}$.
Note that $K_{1}^{\prime}=T(K_{1})$, so $k_{1}$ and $K_{1}^{\prime}$ have the
same winner by induction. Hence, $K$ and $T(K)$ have the same winner, as
required.

Finally, we claim that the $G$ is bipartite if and only if $G^{\prime}$ is
bipartite. First, if $v,w,\ldots,z$ is an odd cycle in $G$, then
$v_{1},w_{1},\ldots,z_{1}$ is an odd cycle in $G^{\prime}$. On the other hand,
if $\left(A,B\right)$ is a bipartition of $G$, then $\left(\left\\{v_{i}:v\in
A\right\\},\left\\{w_{i}:w\in B\right\\}\right)$ is a bipartition of
$G^{\prime}$. ∎

##  3 Directed Geography with Free Deletion

In this section, we add free deletion to both geography and partizan
geography. We obtain that these games, dif and dpf, are both pspace-complete,
even when restricted to bipartite graphs.

###  3.1 Complexity of DIF

We start by proving that dif is pspace-complete on bipartite graphs. Our
reduction is a variation of Lichtenstein and Sipser’s classical reduction from
tqbf to geography, along with their alteration to make the resulting graph
bipartite [geogreduct]. Those authors are also able to place degree
restrictions on the vertices in the resulting graph, but their method for in-
degree restriction does not work under free deletion.

######  Theorem 1.

The game dif is pspace-complete, even when restricted to bipartite graphs.

###### Proof.

We proceed via a reduction from tqbf to dif. Let $Q=\exists x_{1}\forall
x_{2}\cdots\exists x_{n-1}\forall x_{n}c_{1}\wedge c_{2}\wedge\cdots\wedge
c_{m}$ be an instance of tqbf. We construct an instance of dif as follows:

  * •

For each variable $x_{i}$, there is a structure called a _variable gadget_. If
$i$ is even, the variable gadget is a diamond with a pendant. The top vertex
precedes each of the left and right vertices, each of which precedes a vertex
we call the _joining vertex_ , which precedes the pendant (bottom) vertex. If
$i$ is odd, the variable gadget is a hexagon, with a left path and a right
path each with two vertices, a top vertex preceding each of the left and right
paths, and a joining (bottom) vertex succeeding each of the left and right
paths. See Figure 2 for depictions of both types of variable gadget.

  * •

The token begins at the top vertex of the $x_{1}$ gadget.

  * •

For each clause $c_{j}$, there is a structure called a _clause gadget_. It
contains a vertex for the clause and two vertices for each literal in the
clause. If a literal corresponds to an odd-indexed variable or its negation,
the literal vertex succeeds the clause vertex. If a literal corresponds to an
even-indexed variable or its negation, the literal vertex succeeds an extra
vertex, which succeeds the clause vertex. (See Figure 3.)

  * •

For each $i>1$, the bottom vertex of the $x_{i}$ gadget precedes the top
vertex of the $x_{i+1}$ gadget.

  * •

The bottom vertex of the $x_{n}$ gadget precedes each clause vertex.

  * •

A vertex in a clause gadget corresponding to a literal $x_{i}$ for odd $i$
precedes the second vertex in the left path in the $x_{i}$ gadget. A vertex in
a clause gadget corresponding to a literal $\bar{x}_{i}$ for odd $i$ precedes
the second vertex in the right path in the $x_{i}$ gadget.

  * •

A vertex in a clause gadget corresponding to a literal $x_{i}$ for even $i$
precedes the _right_ vertex in the $x_{i}$ gadget. A vertex in a clause gadget
corresponding to a literal $\bar{x}_{i}$ for even $i$ precedes the _left_
vertex in the $x_{i}$ gadget.

See Figure 4 for an example of this construction.

$x_{i}$ odd$1$$0$$J$$x_{i}$ even$1$$0$$J$ Figure 2: Variable gadgets for dif.
Symbols $1$ and $0$ denote vertices corresponding to the variable $x_{i}$
being set to true or false, respectively. Joining vertices are indicated by
the symbol $J$.
$c_{j}$$\ell_{1}$$\ell_{1}$$\ell_{2}$$\ell_{2}$$\ell_{3}$$\ell_{3}$ Figure 3:
Clause gadget for dif, with clause $c_{j}=\ell_{1}\vee\ell_{2}\vee\ell_{3}$,
if the variable in literal $\ell_{3}$ has even index and the others have odd
index.
$T$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$c_{1}$$\bar{x}_{1}$$\bar{x}_{1}$$x_{2}$$x_{2}$$x_{3}$$x_{3}$$c_{2}$$x_{1}$$x_{1}$$x_{3}$$x_{3}$$\bar{x}_{4}$$\bar{x}_{4}$
Figure 4: dif reduction from tqbf instance $\exists x_{1}\forall x_{2}\exists
x_{3}\forall x_{4}\left(\bar{x}_{1}\vee x_{2}\vee
x_{3}\right)\wedge\left(x_{1}\vee x_{3}\vee\bar{x}_{4}\right)$

Let us analyze how the game progresses. First, the token moves through the
variable gadgets, then the token moves through a single clause gadget. After
the token reaches a literal vertex in a clause gadget, there is at most one
more move in the game.

First, let us examine the play options through the variable gadgets. When the
token is at the top vertex of a variable gadget, it is Left’s turn. Several
move/deletion options exist as the token traverses the variable gadget, but we
shall observe that only one decision affects the outcome: which vertex is
deleted when the token is moved to the joining vertex. This decision is key,
and it is important to note that it is made by Left for odd-indexed variables
and by Right for even-indexed variables. After the bottom of the variable
gadget is reached, if more variables remain Right has a forced regular move
from the bottom of the current gadget to the top of the next gadget. Observe
that along the way, every joining vertex is deleted.

After all of the variable gadgets have been traversed, the token is at the
bottom vertex of the $x_{n}$ gadget with Right to move. He can move regularly
to any clause vertex. Left then can select a literal in that clause and move
regularly to a vertex for it if it has odd index or to the extra vertex for it
if it has even index. Note that at least one instance of each literal vertex
is available, as any pair of duplicate literal vertices share a single
successor. It is now Right’s turn. Suppose first that the chosen literal
contains an odd-indexed variable. If the successor of the current vertex has
been deleted, the game is over and Left wins. If not, Right moves to that
vertex and deletes any of its predecessors. Left then loses, as this vertex is
the last vertex in a left or right path in an odd-indexed variable gadget, and
all joining vertices (including this vertex’s only successor) have already
been deleted. On the other hand, suppose that the chosen literal contains an
even-indexed variable. Right is now forced to move regularly to a vertex for
that literal, and it becomes Left’s turn. If the successor of the current
vertex has been deleted, the game is over and Right wins. If not, Left moves
to that vertex and deletes any of its predecessors. Right then loses, as this
vertex is the last vertex in a left or right path in an even-indexed variable
gadget, and all joining vertices (including this vertex’s only successor) have
already been deleted.

We now claim that $Q$ is true if and only if Left wins the corresponding game
of dif. First, suppose $Q$ is true. Then, there is some setting of the
variables $x_{1},x_{3},\ldots,x_{n-1}$ so that the formula is true regardless
of the values of $x_{2},x_{4},\ldots,x_{n}$. Take such a setting, and, as
Left, adopt the following strategy:

  * •

When moving to the joining vertex of the gadget for $x_{i}$, delete the left
predecessor if $x_{i}$ should be set to true, and delete the right predecessor
if $x_{i}$ should be set to false.

  * •

When moving from a clause vertex, choose a successor corresponding to a true
literal.

Since $Q$ is true, every clause is true, which means that each clause contains
a true literal. Right then loses, as the successor of the chosen literal
vertex has been deleted earlier in the game if it contains an odd-indexed
variable, or the successor of the successor of the literal vertex that Right
moves to has not been deleted earlier in the game if it contains an even-
indexed variable.

Now, suppose $Q$ is false. Then, there is some setting of the variables
$x_{2},x_{4},\ldots,x_{n}$ so that the formula is false regardless of the
values of $x_{1},x_{3},\ldots,x_{n-1}$. Take such a setting, and, as Right,
adopt the following strategy:

  * •

When moving to the joining vertex of the gadget for $x_{i}$, delete the left
predecessor if $x_{i}$ should be set to true, and delete the right predecessor
if $x_{i}$ should be set to false.

  * •

When moving to a clause vertex, choose a clause vertex corresponding to a
false clause.

Since $Q$ is false, there is a false clause, which, as a disjunction of
literals, contains no true literal. Right then wins, as the successor of the
literal vertex that Left moves to is still present in the graph if it contains
an odd-indexed variable, or the successor of the literal vertex that Right
moves to is no longer present in the graph if it contains an even-indexed
variable.

This completes the reduction showing that $\text{{tqbf}}\leq_{p}DIF$.
Therefore, dif is pspace-hard, and, hence, pspace-complete, as required.

What remains is to prove that the resulting graph is bipartite (ignoring
direction). We observe that the following describes a bipartition
$\left(A,B\right)$ of the graph.

$A$:

  * •

Top vertices of variable gadgets.

  * •

Second vertices in left and right paths of variable gadgets corresponding to
odd-indexed variables.

  * •

Joining vertices in variable gadgets corresponding to even-indexed variables.

  * •

Clause vertices.

  * •

Literal vertices for even-indexed variables.

$B$:

  * •

First vertices in left and right paths of variable gadgets corresponding to
odd-indexed variables.

  * •

Left and right vertices of variable gadgets corresponding to even-indexed
variables.

  * •

Bottom vertices of variable gadgets.

  * •

Literal vertices for odd-indexed variables.

  * •

Extra vertices in clause gadgets.

∎

###  3.2 Complexity of DPF

In Section 4.2, we prove that the game upf is pspace-complete. By Proposition
3, this implies that dpf is pspace-complete. But, we include a separate proof
here, as this reduction is simpler and yields an underlying bipartite graph.

######  Theorem 2.

The game dpf is pspace-complete, even when restricted to bipartite graphs.

###### Proof.

We proceed via a reduction from tqbf to dpf. Let $Q=\exists x_{1}\forall
x_{2}\cdots\exists x_{n-1}\forall x_{n}c_{1}\wedge c_{2}\wedge\cdots\wedge
c_{m}$ be an instance of tqbf. Without loss of generality, assume that $m\geq
4$ and that $m$ is even (add copies of clauses if this is not the case). We
construct an instance of dpf as follows:

  * •

For each variable $x_{i}$, there is a diamond structure called a _variable
gadget_ , with the top vertex preceding each of the left and right vertices,
each of which precedes the bottom vertex. (See Figure 5.)

  * •

For each clause $c_{j}$, there is a single vertex.

  * •

Left’s token starts at the top vertex of the $x_{1}$ gadget. Right’s token
starts at the top vertex of the $x_{2}$ gadget.

  * •

For $1\leq i<\frac{n}{2}$, the bottom vertex of the $x_{2i-1}$ gadget is also
the top vertex of the $x_{2i+1}$ gadget, and the bottom vertex of the $x_{2i}$
gadget is also the top vertex of the $x_{2i+2}$ gadget.

  * •

There is a path of $2m-3$ vertices, called _delay vertices_. The first delay
vertex succeeds the bottom vertex of the $x_{n-1}$ gadget, and the last delay
vertex precedes each clause vertex.

  * •

There is a path of $2m-3$ vertices, called _clause deletion vertices_. The
first clause deletion vertex succeeds the bottom vertex of the $x_{n}$ gadget.
Each odd-indexed clause deletion vertex succeeds each clause vertex.

  * •

There is a path of $m-1$ vertices, called _escape vertices_. The first escape
vertex succeeds the last clause deletion vertex.

  * •

For each literal $x_{i}$ appearing in clause $c_{j}$, there is a path of $m-3$
vertices succeeding $c_{j}$. The last vertex in this path precedes two
vertices, each of which precede the right vertex in the gadget for $x_{i}$.
For each literal $\bar{x}_{i}$ appearing in clause $c_{j}$, there is a path of
$m-3$ vertices succeeding $c_{j}$. The last vertex in this path precedes two
vertices, each of which precede the left vertex in the gadget for $x_{i}$. We
refer to each such structure linking a clause vertex back to a variable gadget
as a _linker_.

See Figure 6 for a schematic of this construction. Delay vertices are marked
by dly. Clause deletion vertices are marked by dlt. Escape vertices are marked
by esc. Linker vertices are marked by lnk. There are several linkers that are
not pictured; only the linkers from $c_{1}$ are shown.

$x_{i}$$1$$0$ Figure 5: Variable gadget for dpf. Symbols $1$ and $0$ denote
vertices corresponding to the variable $x_{i}$ being set to true or false,
respectively.
$L$$x_{1}$$R$$x_{2}$$x_{3}$$x_{4}$$\vdots$$\vdots$$x_{n-1}$$x_{n}$$\text{{dly}}_{1}$$\text{{dlt}}_{1}$$\text{{dly}}_{2}$$\text{{dlt}}_{2}$$\text{{dly}}_{3}$$\text{{dlt}}_{3}$$\vdots$$\text{{dly}}_{2m-3}$$\vdots$$\text{{dlt}}_{2m-3}$$c_{1}$$c_{2}$$c_{3}$$\vdots$$c_{m}$$\text{{esc}}_{1}$$\text{{esc}}_{2}$$\vdots$$\text{{esc}}_{m-1}$$\text{{lnk}}_{1}$$\text{{lnk}}_{2}$$\vdots$$\text{{lnk}}_{m-3}$$\text{{lnk}}_{1}$$\text{{lnk}}_{2}$$\vdots$$\text{{lnk}}_{m-3}$$\text{{lnk}}_{1}$$\text{{lnk}}_{2}$$\vdots$$\text{{lnk}}_{m-3}$
Figure 6: Schematic diagram dpf construction from tqbf instance $\exists
x_{1}\forall x_{2}\cdots\exists x_{n-1}\forall x_{n}\left(x_{1}\vee
x_{2}\vee\bar{x}_{4}\right)\wedge c_{2}\wedge\cdots\wedge c_{m}$. Linkers
succeeding $c_{2}$ through $c_{m}$ exist but are not shown.

Let us analyze how the game progresses. First, the tokens moves through the
variable gadgets. Then, Left’s token traverses the delay vertices while
Right’s token traverses the clause deletion vertices. After $m-1$ moves by
each player, both tokens are at the bottom of their respective structures,
with Left to move. Left moves to a clause vertex. We observe later how the
game proceeds from here.

First, let us examine the play options through the variable gadgets. When the
active player’s token is at the top vertex of the gadget for $x_{i}$, the
active player has two move options (the left and right vertices in the
gadget), and that player can delete the top vertex of the gadget or any vertex
in a linker preceding the vertex moved to. Neither this move nor this deletion
affects the outcome. The move after this decision is forced, to the bottom of
the gadget, but either the left or right vertex of the gadget can be deleted.
This decision is key, and it is important to note that these decisions are
made in order of the index of the variables by alternating players, starting
with Left.

After all of the variable gadgets have been traversed, Left’s token is at the
bottom of the $x_{n-1}$ gadget, and Right’s token is at the bottom of the
$x_{n}$ gadget, with Left to move. Her next $2m-3$ moves are forced to
regularly traverse the chain of delay vertices. Meanwhile, Right makes $2m-3$
moves through the clause deletion vertices. After each move to an odd-indexed
clause deletion vertex, he can delete any remaining clause vertex, or he can
delete the vertex he moved from. Not deleting a clause when able only serves
to give Left more options later in the game, so Right can do no better than to
always delete clause vertices. Right’s moves to even-indexed clause deletion
vertices are forced to be regular. When Left is to move from the last delay
vertex, Right’s token is at the last clause deletion vertex, and there is one
clause vertex that has not been deleted. Left is forced to move regularly to
that vertex. Then, Right is forced to move regularly to the first escape
vertex (deleting the last clause deletion vertex). Now, all of the odd-indexed
clause deletion vertices have been deleted, so Left must move to a linker.

Once in a linker, Left’s next $m-4$ moves are regular and forced along a path.
The move after that is also regular to one of the two last vertices of the
linker, at least one of which remains. At that point, Left is out of moves if
the vertex in the variable gadget succeeding the linker has been deleted and
can move to that vertex otherwise. So, Left has $m-3$ moves remaining if she
chooses a linker that no longer connects to a variable gadget, and she has at
least $m-2$ moves remaining if the linker does still connect. Since Right
moves next with $m-2$ moves remaining in the escape path, Left wins if and
only if the linker still connects to a variable gadget.

We now claim that $Q$ is true if and only if Left wins the corresponding game
of dpf. First, suppose $Q$ is true. Then, there is some setting of the
variables $x_{1},x_{3},\ldots,x_{n-1}$ so that the formula is true regardless
of the values of $x_{2},x_{4},\ldots,x_{n}$. Take such a setting, and, as
Left, adopt the following strategy:

  * •

When moving to the bottom vertex of the gadget for $x_{i}$, delete the left
vertex if $x_{i}$ should be set to true, and delete the right vertex if
$x_{i}$ should be set to false.

  * •

When moving from a clause vertex, enter a linker corresponding to a true
literal.

Since $Q$ is true, at least one of the remaining clause’s literals is true.
The successor of the linker from that clause vertex corresponding to that
literal has not been deleted.

Now, suppose $Q$ is false. Then, there is some setting of the variables
$x_{2},x_{4},\ldots,x_{n}$ so that the formula is false regardless of the
values of $x_{1},x_{3},\ldots,x_{n-1}$. Take such a setting, and, as Right,
adopt the following strategy:

  * •

When moving to the bottom vertex of the gadget for $x_{i}$, delete the left
vertex if $x_{i}$ should be set to true, and delete the right vertex if
$x_{i}$ should be set to false.

  * •

For some $j$ such that clause $c_{j}$ is false, avoid deleting the vertex
corresponding to $c_{j}$ (so that Left is forced to move there).

As we have seen, later in the game, Left moves to the clause vertex
corresponding to $c_{j}$. This clause is false, so all of its literals are
false. So, the successors of every linker from that clause vertex have been
deleted, so Right wins.

This completes the reduction showing that $\text{{tqbf}}\leq_{p}DPF$.
Therefore, dpf is pspace-hard, and, hence, pspace-complete, as required.

Finally, we claim that the underlying graph in the dpf instance is bipartite.
Consider the partition $\left(A,B\right)$ as follows:

$A$:

  * •

Top and bottom vertices of variable gadgets.

  * •

Even-indexed delay vertices.

  * •

Even-indexed clause deletion vertices.

  * •

Clause vertices.

  * •

Both vertices in each linker that precede a node in a variable gadget.

  * •

Remaining linker vertices that are not in $B$.

  * •

Odd-indexed escape vertices.

$B$:

  * •

Left and right vertices of variable gadgets.

  * •

Odd-indexed delay vertices.

  * •

Odd-indexed clause deletion vertices.

  * •

Alternating vertices along the path in each linker, starting with the vertex
that succeeds a clause vertex.

  * •

Even-indexed escape vertices.

We claim that $\left(A,B\right)$ is a bipartition. We check a few potential
problem spots; the rest of the claim is obvious. First, since $2m-3$ is odd,
the last delay vertex is in $B$. This is consistent with the clause vertices
being in $A$. Similarly, the clause vertices only precede odd-indexed clause
deletion vertices, all of which are in $B$. Finally, $m-3$ is odd (since $m$
is even), so the linker vertices that precede two vertices in a linker are in
$B$. Their successors are in $A$, and the successors of those vertices, as
left or right vertices in variable gadgets, are in $B$, as required. ∎

##  4 Undirected Partizan Geography

In this section, we analyze the games upr and upf, both of which are pspace-
complete.

###  4.1 Complexity of UPR

The game upr is often referred to as undirected partizan geography. It is
previously known to be np-hard, via a reduction from the Hamiltonian path
problem [fsugeog]. We prove now that undirected partizan geography is, in
fact, pspace-hard, even when restricted to bipartite graphs.

######  Theorem 3.

The game upr is pspace-complete, even when restricted to bipartite graphs.

###### Proof.

We proceed via a reduction from tqbf to upr on bipartite graphs. Let
$Q=\exists x_{1}\forall x_{2}\cdots\exists x_{n-1}\forall x_{n}c_{1}\wedge
c_{2}\wedge\cdots\wedge c_{m}$ be an instance of tqbf. Without loss of
generality, assume that $n\geq 4$, that $m\geq 2$, and that every literal
appears in some clause. (If this is not the case, append a cause of the form
$x_{i}\vee x_{i}\vee\bar{x}_{i}$ for any literal $x_{i}$ or $\bar{x}_{i}$ not
appearing.) We construct an instance of upr as follows.

  * •

For each variable $x_{i}$, there is a diamond structure called a _variable
gadget_ , with the top vertex adjacent to each of the left and right vertices,
each of which is adjacent to the bottom vertex (much like the variable gadget
for dpf, but with undirected edges).

  * •

Left’s token starts at the top vertex of the $x_{1}$ gadget. Right’s token
starts at the top vertex of the $x_{2}$ gadget.

  * •

For $1\leq i<\frac{n}{2}$, the bottom vertex of the $x_{2i-1}$ gadget is also
the top vertex of the $x_{2i+1}$ gadget, and the bottom vertex of the $x_{2i}$
gadget is also the top vertex of the $x_{2i+2}$ gadget.

  * •

There is a complete bipartite graph $K_{m,m-1}$ called the _clause selection
gadget_. The vertices on the side with $m$ vertices correspond to the clauses;
these are called _clause vertices_. (See Figure 7.)

  * •

Each clause vertex is adjacent to the bottom vertex of the $x_{n}$ gadget.

  * •

There is a complete bipartite graph $K_{m+\frac{n}{2}+5,m+\frac{n}{2}+5}$
called the _delay graph_ , with its two parts known as _Part I_ and _Part II_.
All vertices in Part I are adjacent to the bottom vertex of the $x_{n-1}$
gadget.

  * •

There is a vertex called exit that is adjacent to the bottom vertex of the
$x_{n-1}$ gadget and adjacent to every vertex in Part II of the delay graph.

  * •

There is a path linking exit to each clause vertex. There are $n+4$ vertices
along this path not including exit or the clause vertex. Each such path is
known as a _clause connector_.

  * •

For each literal $x_{i}$ appearing in clause $c_{j}$, there are two
independent paths from the vertex for $c_{j}$ to the right vertex in the
gadget for $x_{i}$. For each literal $\bar{x}_{i}$ appearing in clause
$c_{j}$, there are two independent paths from the vertex for $c_{j}$ to the
left vertex in the gadget for $x_{i}$. If $i$ is odd, there are $n+2$ vertices
along each path, not including the clause vertex or the vertex in the variable
gadget. If $i$ is even, there are $n+7$ vertices along each path, not
including the clause vertex or the vertex in the variable gadget. We refer to
each such path linking a clause vertex back to a variable gadget as a
_linker_. (Each clause vertex has six linkers attached to it). If $i$ is odd,
we call the path a _left-linker_ , and if $i$ is even, we call it a _right-
linker_.

  * •

There is a path of $3n+25$ vertices, known as _escape vertices_. The first
escape vertex is adjacent to each non-clause vertex in the clause selection
gadget.

See Figure 8 for a schematic of this construction. Escape vertices are marked
by esc. The clause selection gadget is the complete bipartite graph below
Right’s variable gadgets. The delay graph is the complete bipartite graph
below Left’s variable gadgets. The clause connectors are the paths between
exit and the clauses. The paths connecting $c_{1}$ to the right vertex of the
$x_{1}$ gadget are left-linkers and contain $n+2$ vertices each. The paths
connecting $c_{1}$ to other variable gadgets are right-linkers and contain
$n+7$ vertices each. There are several linkers that are not pictured; only the
linkers adjacent to $c_{1}$ are shown.

$c_{1}$$c_{2}$$c_{3}$$c_{4}$$\vdots$$c_{m}$$\vdots$$m-1$non-clausevertices
Figure 7: Clause selection gadget for upr.
$L$$x_{1}$$R$$x_{2}$$x_{3}$$x_{4}$$\vdots$$\vdots$$x_{n-1}$$x_{n}$$\vdots$$c_{1}$$c_{2}$$c_{3}$$\vdots$$c_{m}$$\textsc{esc}_{1}$$\textsc{esc}_{2}$$\textsc{esc}_{3}$$\vdots$$\textsc{esc}_{3n+25}$$\vdots$$\vdots$exit$m+\frac{n}{2}+5$vertices$\cdots$$\cdots$$\cdots$$\vdots$$\vdots$$\cdots$$n+4$
vertices$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$n+2$vertices$n+7$vertices
Figure 8: Schematic diagram upr construction from tqbf instance $\exists
x_{1}\forall x_{2}\cdots\exists x_{n-1}\forall x_{n}\left(x_{1}\vee
x_{2}\vee\bar{x}_{4}\right)\wedge c_{2}\wedge\cdots\wedge c_{m}$. Linkers
adjacent to $c_{2}$ through $c_{m}$ exist but are not shown.

We claim first that the graph is bipartite. Note that each individual building
block is bipartite, as each is a $4$-cycle, a path, or a complete bipartite
graph. Consider the following partition of the graph into two parts, $A$ and
$B$:

$A$:

  * •

Top and bottom vertices of the gadgets for variables $x_{i}$ for odd $i$

  * •

Left and right vertices of the gadgets for variables $x_{i}$ for even $i$

  * •

Part II of the delay graph

  * •

Every other vertex of each clause connector, starting with the vertex adjacent
to exit

  * •

The clause vertices

  * •

Every other escape vertex, starting with the first one

  * •

The vertices in linkers not in $B$.

$B$:

  * •

Left and right vertices of the gadgets for variables $x_{i}$ for odd $i$

  * •

Top and bottom vertices of the gadgets for variables $x_{i}$ for even $i$

  * •

Part I of the delay graph

  * •

exit

  * •

The vertices in clause connectors not in $A$

  * •

The vertices in the clause selection gadget that are not clause vertices

  * •

Every other escape vertex, starting with the second one

  * •

Every other vertex in each linker, starting with the vertex adjacent to a
clause vertex.

We claim that this is a bipartition of the graph. There are only three things
to check that aren’t immediately clear. First, since $n+4$ is even, the vertex
of a clause connector adjacent to a clause vertex is in $B$ (since the vertex
adjacent to exit is in $A$). The clause vertices are in $A$, as required.
Second, since $n+2$ is even, the vertex in each left-linker adjacent to a
variable vertex is in $A$ (since the vertex adjacent to a clause vertex is in
$B$). That variable vertex is a left or right vertex of a gadget for $x_{i}$
with $i$ odd, so it is in $B$, as required. Finally, since $n+7$ is odd, the
vertex in each right-linker adjacent to a variable vertex is in $B$ (since the
vertex adjacent to a clause vertex is also in $B$). That variable vertex is a
left or right vertex of a gadget for $x_{i}$ with $i$ even, so it is in $A$,
as required.

Since Left’s token starts in $A$ and Right’s token starts in $B$, it is always
Left’s turn if the tokens are in opposite parts and Right’s turn if the tokens
are in the same part. For convenience, we refer to this property as the
_bipartite move invariant_. A key consequence of the bipartite move invariant
is that it is always Left’s turn if the tokens are on adjacent vertices.

Here is one possible way the game could progress, which we refer to as _proper
play_ : First, in what we call _Phase I_ , the tokens move downward through
the variable gadgets. At the end of Phase I, it is Left’s turn, with Left’s
token at the bottom of the gadget for $x_{n-1}$ and Right’s token at the
bottom of the gadget for $x_{n}$. Then, to start Phase II, Left’s token enters
Part I of the delay graph immediately before Right’s token enters a clause
vertex. Left’s next $2m-3$ moves take place in the delay graph, while Right’s
next $2m-3$ moves take place in the clause selection gadget. After all of
these moves, Left is at some vertex in Part II of the delay graph, while Right
is at the only remaining non-clause vertex in the clause selection gadget.
Moreover, only one clause vertex remains. It is now Left’s move, and she moves
back to Part I of the delay graph. Right then moves to the first escape
vertex. All of Right’s subsequent moves take place in the escape path. Left
moves through all remaining vertices in the delay graph and, exhausting all of
those, moves to exit. From there, she moves along the clause connector to
whichever clause vertex $c_{j}$ still remains. Upon reaching that clause, she
departs via some linker. If she chooses a left-linker and she reaches a vertex
in a variable gadget, she continues into another linker attached to that
vertex.

We have the following claims, which would complete our reduction:

  * •

If the game must progress according to proper play, then $Q$ is true if and
only if Left wins the game of upr.

  * •

Neither player can do better than to play properly.

For the time being, assume that the game must progress properly. First,
suppose $Q$ is true. Then, there is some setting of the variables
$x_{1},x_{3},\ldots,x_{n-1}$ so that the formula is true regardless of the
values of $x_{2},x_{4},\ldots,x_{n}$. Take such a setting, and, as Left, adopt
the following strategy:

  * •

When moving from the top vertex of the gadget for $x_{i}$, move to the left
vertex if $x_{i}$ should be set to true, and move to the right vertex if
$x_{i}$ should be set to false.

  * •

When moving from a clause vertex, enter a linker corresponding to a true
literal.

Since $Q$ is true, at least one of that clause’s literals is true. As a
result, the vertex in a variable gadget that that linker connects to the
clause vertex is still present. Regardless of whether it is a left-linker or a
right-linker, Left has at least $n+8$ moves remaining when her token lies on
the clause vertex. If the linker is a left linker, there are $n+2$ moves to
vertices along the linker, one move to a vertex in a variable gadget, and five
moves into another linker (since $n+2$, the number of vertices in a left
linker, is at least $5$). If the linker is a right-linker, there are $n+7$
moves to vertices along the linker and one move to a vertex in a variable
gadget. Now, consider the position at the end of Phase I. Right has $2m+3n+23$
moves remaining: $2m-2$ moves in the clause gadget, followed by $3n+25$ moves
in the escape path. Left has at least $2m+3n+24$ moves remaining: $2m+n+10$
moves in the delay graph, $1$ move to exit, $n+4$ moves through a clause
connector, $1$ move into a clause vertex, and $n+8$ moves after the clause
vertex. Therefore, Left wins, as required.

Now, suppose $Q$ is false. Then, there is some setting of the variables
$x_{2},x_{4},\ldots,x_{n}$ so that the formula is false regardless of the
values of $x_{1},x_{3},\ldots,x_{n-1}$. Take such a setting, and, as Right,
adopt the following strategy:

  * •

When moving from the top vertex of the gadget for $x_{i}$, move to the left
vertex if $x_{i}$ should be set to true, and move to the right vertex if
$x_{i}$ should be set to false.

  * •

For some $j$ such that clause $c_{j}$ is false, avoid moving to the vertex
corresponding to $c_{j}$ while traversing the clause selection gadget.

Around the end of the game, Left moves to the vertex for $c_{j}$. Since
$c_{j}$ is false, all of that clause’s literals are false. This means that
Left has at most $n+7$ moves remaining from the clause vertex, since each
linker from $c_{j}$ no longer connects to a variable gadget. Now, consider the
position at the end of Phase I. Right has $2m+3n+23$ moves remaining, as we
saw in the previous case. Left has at most $2m+3n+23$ moves remaining:
$2m+n+10$ moves in the delay graph, $1$ move to exit, $n+4$ moves through a
clause connector, $1$ move into a clause vertex, and $n+7$ moves after the
clause vertex. Therefore, Right wins, as required.

What remains to show is that neither player can do better by deviating from
proper play. Each player has several ways in which they can deviate. We
analyze each possible deviation one at a time, supposing that it is the first
deviation that has taken place in the game thus far.

Left enters a linker from a variable gadget:

Suppose Left enters a linker connected to the clause vertex for $c_{j}$. When
Left enters a linker, Right’s token is on the left or right vertex of a
variable gadget. Such a vertex is at most $n$ moves from the clause vertex for
$c_{j}$ if Right continues down through the variable gadgets. (At worst, Right
is in the $x_{2}$ gadget. There are $\frac{n}{2}$ gadgets, each requiring two
moves to traverse. One move of the first gadget is already complete, and there
is one additional move required to reach a clause.) Since it requires $n+3$
moves for Left to reach the vertex for $c_{j}$ via the linker, Right can reach
$c_{j}$ before Left, deleting it as he moves elsewhere, forcing Left to run
out of moves at the end of the linker.

Left moves upward from the bottom vertex of a variable gadget:

Moving upward in a variable gadget forces the subsequent move to be into a
linker. Right can proceed as in the previous case, now having even more time
to reach the appropriate clause vertex before Left. There is one small
additional consideration: If Left moves upward from the bottom of the
$x_{n-1}$ gadget, Right does not know which clause she will head for and must
now move to a clause himself. But, he can move to any clause, after which Left
commits to a clause. Then, Right takes two more moves to reach that clause.
From there, Right can move into the clause connector, and Left runs out of
moves first, since left-linkers are shorter than clause connectors.

Left moves to exit before visiting the whole delay graph:

From exit, Left can either move back into the delay graph or into a clause
connector. If she returns to the delay graph, she is trapped there, running
out of moves while Right plays properly. So, we henceforth assume that Left
moves to exit with the intent to move next into a clause connector. Now,
observe that, if Right has not yet entered the escape path when Left moves to
exit, the bipartite move invariant implies that Right’s token is not on a
clause vertex; it must be in the same part ($B$) of the underlying graph as
exit. There are two sub-cases to consider regarding the situation when Left
moves to exit.

At least two clause vertices remain:

After Left moves to exit, Right moves to any clause vertex. Then, Left
definitely loses if she moves toward the clause vertex Right’s token currently
occupies or toward a deleted clause vertex, so she moves toward a remaining
clause vertex. Right then moves to a non-clause vertex in the clause selection
gadget and then to the clause vertex that Left is headed for. From there,
Right enters the same clause connector that Left is currently traversing. By
the bipartite move invariant, it is Left’s move when the tokens are adjacent.
This results in Left losing, as required.

Exactly one clause vertex remains:

If the remaining clause is true, Left would win anyway, so we can assume that
the remaining clause is false and that Left is trying to win when $Q$ is
false. From this point forward, Left’s only option is to follow proper play,
running out of moves sooner than if she had not left the delay graph early.
Therefore, if Right continues according to proper play, Left loses.

Right enters a linker from a variable gadget:

Suppose Right enters a linker connected to the clause vertex for $c_{j}$. When
Right enters a linker, Left’s token is at the bottom of a variable gadget.
Such a vertex is at most $n+6$ moves from the clause vertex for $c_{j}$, if
Left moves up the current variable gadget (one move), through a linker to a
clause vertex ($n+2$ moves in the linker plus one to the clause vertex), and
if necessary, through the clause selection gadget to $c_{j}$ ($2$ moves).
Since it requires $n+7$ additional moves for Right to reach the vertex for
$c_{j}$ via the right-linker after entering it, Left can reach the vertex for
$c_{j}$ before Right, causing Right to run out of moves at the end of the
linker.

Right moves upward from the bottom vertex of a variable gadget:

Moving upward in a variable diamond forces the subsequent move to be into a
linker. If Left’s token is still in a variable gadget, it is on a left or
right vertex, and Left can proceed as in the previous case, now having even
more time to reach the appropriate clause vertex before Right. The other
possibility is that Left’s token is in Part I of the delay graph. In this
case, Left’s next move is to any vertex in Part II, after which Right commits
to a clause $c_{j}$. Then, Left moves to exit and heads for the vertex for
$c_{j}$ via the clause connector. The total number of moves required by Left
to reach the vertex for $c_{j}$ once Right deviates from proper play is $n+7$
(one in the delay graph, one to exit, $n+4$ through the clause connector, and
one to $c_{j}$), and Right needs $n+8$ moves to reach $c_{j}$ _after_
deviating ($n+7$ through the linker and one to the vertex for $c_{j}$).
Therefore, Left reaches the vertex for $c_{j}$ before Right and wins.

Right moves into a linker from a clause vertex:

We can assume without loss of generality that the variable vertex at the end
of the linker Right enters is still present in the graph, as otherwise Left
can continue moving properly while Right runs out of moves. This means that
Right reaches that variable vertex and then immediately enters another linker.
By the bipartite move invariant, when Right moves into a linker (from $A$ to
$B$), Left’s token is in Part II of the delay graph (in $A$). There are two
sub-cases to consider:

Right enters a left-linker:

In this case, Left can immediately move to exit, and then she can enter any
clause connector toward a remaining clause. It takes $n+6$ moves for Left to
reach a clause. After $n+6$ moves, since Right originally entered a left-
linker, he has already passed through the variable vertex and has therefore
committed to a linker to return along back to the clause selection gadget. If
the clause vertex at the end of that linker still remains, Left can move to it
through the clause selection gadget in two more moves, and then she can exit
through the clause connector, after which Right runs out of moves first. It
takes Left $n+8$ moves to reach this second clause vertex, and it takes Right
$2n+6$ moves to reach it, with Right moving first. Since $n\geq 4$, we have
$n+8<2n+6$, so Left does indeed reach the clause vertex first, and since
$n+2<n+4$, Right does indeed run out of moves first.

Right enters a right-linker:

In this case, Left should move back to Part I of the delay graph, then back to
Part II, then back to Part I, then back to Part II, then to exit. Then, she
can enter any clause connector toward a remaining clause. It takes $n+10$
moves for Left to reach a clause this way. After $n+10$ moves, Right’s token
has entered another linker after visiting a variable vertex, and Right moves
next and reaches a clause vertex (if it is still present) in $n+6$ more moves.
If there is no clause that Right is headed toward, Left heads for the escape
path and wins. If there is a clause vertex that Right is headed toward, Left
reaches that clause in two moves and then enters the clause connector. This is
a total of $n+6$ more moves for Left (two in the clause selection gadget and
$n+4$ through the clause connector). Since Right moves first from this
checkpoint, Right runs out of moves first and loses.

Right moves into a clause connector from a clause vertex:

By the bipartite move invariant, when Right moves into a clause connector
(into $B$), Left’s token is in Part II of the delay graph (in $A$). Left can
immediately move to exit, and then she can enter any other clause connector.
Right runs out of moves first, when he reaches the vertex in his clause
connector that was once adjacent to exit.

Right moves into the last clause vertex instead of the escape path:

This forces Right’s next move to be into a clause connector or a linker. If
Right moves into a clause connector, play continues according to that case
above, with Left winning. If Right moves into a linker, right has at most
$2n+14$ moves remaining after doing so, as there is no clause remaining to
return to along a second linker. So, after Phase I ends, Right has at most
$2m+2n+14$ remaining moves, accounting for all $2m-1$ vertices in the clause
gadget and $2n+15$ moves afterward. At this same point, Left has $2m+n+10$
moves in the delay graph, $1$ move to exit, and $n+4$ moves through a clause
connector. This is a total of $2m+2n+15$ moves, so Right runs out of move
first and loses.

Right moves into the escape path with multiple remaining clause vertices:

If all remaining clauses are false, Right would win by playing properly, so we
can assume that at least one clause is true and that Right is trying to win
when $Q$ is true. Once Right enters the escape path, he can never leave it,
and he has exactly $2n+24$ moves afterward. This means that Left can now
continue properly, exhausting the delay graph, then traveling to a remaining
true clause vertex and into a linker corresponding to a true literal. Right
has fewer moves than before, so Right still runs out of moves before Left.

This completes the reduction showing that $\text{{tqbf}}\leq_{p}\textsc{upr}$.
Therefore, upr is pspace-hard on bipartite graphs, and, hence, pspace-
complete, as required. ∎

###  4.2 Complexity of UPF

We now prove that the related game upf is also pspace-complete. In this case,
our construction is not bipartite333This construction depends critically on
odd cycles (here $13$-cycles) resulting from the way variable gadgets are
attached to one another..

######  Theorem 4.

The game upf is pspace-complete.

###### Proof.

We proceed via a reduction from tqbf to upf. Let $Q=\exists x_{1}\forall
x_{2}\cdots\exists x_{n-1}\forall x_{n}c_{1}\wedge c_{2}\wedge\cdots\wedge
c_{m}$ be an instance of tqbf. Without loss of generality, assume that $m\geq
3$. We construct an instance of upf as follows:

  * •

For each variable $x_{i}$, we have what we call the _variable gadget,_ which
consists of two disjoint pieces: a cycle with $8$ vertices and a path with $5$
vertices. We draw and refer to the cycle as a _diamond_ , allowing us to
define its top, leftmost, rightmost, and bottom vertices. We draw the path
vertically with the first vertex on top. See Figure 9 for a depiction of a
variable gadget.

  * •

Left’s token starts at the top vertex of the $x_{1}$ diamond. Right’s token
starts at the first vertex of the $x_{1}$ path.

  * •

For $1\leq i<n$, the bottom vertex of the $x_{i}$ diamond is adjacent to the
first vertex of the $x_{i+1}$ path, and the fourth vertex of the $x_{i}$ path
is adjacent to the top vertex of the $x_{i+1}$ diamond.

  * •

For $1\leq i\leq n$, the bottom vertex of the $x_{i}$ diamond is adjacent to
the fifth vertex of the $x_{i}$ path.

  * •

There is a graph called the _clause selection gadget_ , which consists of
several pieces. See Figure 10 for a depiction of the clause selection gadget;
what follows are descriptions of the pieces and how they are interconnected.

    * –

There are designated top and bottom vertices. The top vertex of the clause
selection gadget is also the bottom vertex of the $x_{n}$ diamond.

    * –

For each clause $c_{j}$, there is a single vertex.

    * –

There are $m$ paths enumerated from $1$ to $m$, called _clause deletion paths_
, of $m+3$ vertices each. The first vertex of each clause deletion path is
adjacent to the top vertex of the clause selection gadget. The last vertex of
each clause deletion path is adjacent to the bottom vertex of the clause
selection gadget.

    * –

Each vertex in each clause deletion path other than the first, second, second-
to-last, and last, is adjacent to a clause vertex. The vertex for clause
$c_{j}$ is adjacent to some vertex in every clause deletion path except for
the $j^{th}$ path. Along a path, the indices of the adjacent clause vertices
appear in increasing order.

  * •

There is a path of $m+9$ vertices called the _delay path_. The first delay
vertex is adjacent to the fourth vertex in the path for $x_{n}$.

  * •

There is a path linking the last delay vertex to each clause vertex. There are
$m$ vertices along this path, not including the delay vertex and the clause
vertex. Each such path is called a _clause connector_.

  * •

For each literal $x_{i}$ appearing in clause $c_{j}$, there is a path from the
vertex for $c_{j}$ to the right vertex in the diamond for $x_{i}$. For each
literal $\bar{x}_{i}$ appearing in clause $c_{j}$, there is a path from the
vertex for $c_{j}$ to the left vertex in the diamond for $x_{i}$. There are
$m+3$ vertices along each path, not including the clause vertex and the
variable vertex. We refer to each such path linking a clause vertex back to a
variable gadget as a _linker_.

  * •

There is a path of $8m+7$ vertices, known as the _escape path_. The first
escape vertex is adjacent to the bottom vertex of the clause selection gadget.

  * •

There is a vertex called prize adjacent to the third escape vertex and the
$\left(m+7\right)^{th}$ delay vertex.

  * •

There is a path, called the _win path_ , of $13n+5m^{2}+22m+21$ vertices. The
first win vertex is adjacent to prize and to the fifth vertex of each path in
each variable gadget.

Observe that the number of vertices in the win path is two greater than the
number of vertices in the graph outside the win path. (There are $13n$
vertices in variable gadgets, $2+m+m\left(m+3\right)$ in the clause gadget,
$m+9$ delay vertices, $m\left(m+3\right)$ total in the clause connectors,
$3m^{2}$ total in the linkers, $8m+7$ escape vertices, and $1$ prize vertex.)

See Figure 11 for a schematic of this construction. There are several linkers
that are not pictured; only the linkers from $c_{1}$ are shown. Also, there
are edges between clause vertices and omitted vertices in clause deletion
paths, and there are edges from omitted variable gadgets to the first win
vertex.

$1$$0$$x_{i}$ Figure 9: Variable gadget for upf. Symbols $1$ and $0$ denote
vertices corresponding to the variable $x_{i}$ being set to true or false,
respectively. $c_{1}$$c_{2}$$c_{3}$$c_{4}$$c_{5}$ Figure 10: Clause selection
gadget for upf with $m=5$
$L$$R$$x_{1}$$x_{2}$$\vdots$$\vdots$$x_{n}$$\vdots$$\vdots$$\vdots$Win
Path$13n+5m^{2}+22m+21$ vertices$\vdots$Delay Path$m+9$
vertices$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$c_{1}$$c_{2}$$\vdots$$c_{m}$$\vdots$Escape
Path$8m+7$ verticesprize$\cdots$$\cdots$$\vdots$$\vdots$$\cdots$Clause
Connectors$m$ vertices each$\vdots$$\vdots$$\vdots$Linkers$m+3$ vertices each
Figure 11: Schematic diagram upf construction from tqbf instance $\exists
x_{1}\forall x_{2}\cdots\exists x_{n-1}\forall x_{n}\left(x_{1}\vee
x_{2}\vee\bar{x}_{n}\right)\wedge c_{2}\wedge\cdots\wedge c_{m}$. Linkers
adjacent to $c_{2}$ through $c_{m}$ exist but are not shown.

Here is one possible way the game could progress, which we refer to as _proper
play_. We split the progression into three phases:

Phase I:

This phase consists of one round for each variable gadget, along with a move
by each player between each pair of successive rounds. The rounds for odd-
indexed variables are begun by Left; the rounds for even-indexed variables are
begun by Right. In a single round, four moves are made by the first player and
three by the second. Whichever player begins spends their moves moving from
the top vertex of the diamond to the bottom vertex of the diamond. They delete
the top vertex on the first move and the left or right vertex on the third
move (whichever direction they choose to travel). The second move can either
delete the vertex moved from or a vertex in a linker. The fourth move must
delete the fifth vertex in the path for this variable if it is still present.
Otherwise, it can delete either neighbor in the current diamond. The other
player spends their three moves moving regularly along their path, except that
the third move is also permitted to delete the fifth vertex in the path.

Between successive rounds, the player in the path, currently on its fourth
vertex, makes a regular move to the top vertex of the next variable’s diamond,
and then the player in the diamond, currently in its bottom vertex, moves
regularly to the first vertex of the next variable’s path.

Phase II:

This phase begins after the final round of Phase I, with Left’s token on the
fourth vertex of the $x_{n}$ path, Right’s vertex on the bottom vertex of the
$x_{n}$ diamond, and Left to move. It consists of $m+7$ moves by each player.
All of Left’s moves in Phase II are regular moves through the delay path.
Right’s first $m+4$ moves are through the clause selection gadget, along one
of the clause deletion paths. On each move that ends adjacent to a clause
vertex, Right deletes that clause vertex, resulting in the deletion of all but
one clause vertex. The rest of Right’s moves through the clause selection
gadget are regular, with the possible exception of the move to the bottom of
the gadget, which can delete any neighbor in the clause selection gadget.
Right’s subsequent three moves are into and along the escape path. The first
two of these moves are regular; the third deletes prize.

Phase III:

This phase begins with Left in the delay path on the vertex that was adjacent
to prize before Right deleted it and with Right in the escape path on the
vertex that was adjacent to prize. It is Left’s turn. Here is the sequence of
moves Left makes:

  * •

First, she continues to move regularly through the delay path.

  * •

Next, she enters the _clause connector stalling stage_. There are $m-1$ clause
connectors that are no longer connected to a clause. She moves into one of
them, deleting the subsequent vertex in that connector, then she returns
regularly to the last delay vertex. She does this two move sequence for each
of these $m-1$ clause connectors.

  * •

Once those moves are all done, she enters and moves regularly along the clause
connector connected to the one remaining clause vertex until she reaches the
clause vertex.

  * •

Now, Left enters the _clause deletion path stalling stage_. The clause vertex
is adjacent to $m-1$ vertices in $m-1$ clause deletion paths, which have no
connections remaining between them except through the clause vertex. She moves
into one of the clause deletion paths, deleting the vertex in that path below
the vertex moved to. Then, she moves upward along the path, deleting the
vertex above the one moved to. She then takes two regular moves to return to
the clause vertex. She does this four move sequence for each of the $m-1$
clause deletion paths. See Figure 12 for an illustration of this four move
sequence.

  * •

Once those moves are all done, she enters the _linker stalling stage_. The
clause vertex is adjacent to three linkers. She moves into one of them,
deleting the second vertex, then she returns regularly to the clause vertex.
Left then repeats this process for a second linker.

  * •

Finally, Left enters and moves along the third linker, potentially reaching a
variable diamond.

Meanwhile, Right’s moves are all regular along the escape path.

Note that, in Phase III, Left makes two moves in the delay path, followed by
$2m-2$ moves in the clause connector stalling stage, followed by $m$ moves
through the last clause connector and one move to the clause vertex, followed
by $4m-4$ moves in the clause deletion path stalling stage, followed by four
moves in the linker stalling stage. So, when Left is on the clause vertex
about to enter the last linker, she has made a total of $7m+1$ moves (and
therefore Right has made the same number of moves).

$c_{j}$4132 Figure 12: Illustration of the clause deletion path stalling stage
of Phase III. Arrows indicate moves; numbers indicate order vertices are
deleted.

We have the following claims, which would complete our reduction:

  * •

If the game must progress properly, then $Q$ is true if and only if Left wins
the game of upf.

  * •

Neither player can do better than to move properly.

For the time being, assume that the game must progress properly. First,
suppose $Q$ is true. Then, there is some setting of the variables
$x_{1},x_{3},\ldots,x_{n-1}$ so that the formula is true regardless of the
values of $x_{2},x_{4},\ldots,x_{n}$. Take such a setting, and, as Left, adopt
the following strategy:

  * •

When moving from the top vertex of the diamond for $x_{i}$, move left if
$x_{i}$ should be set to true, and move right if $x_{i}$ should be set to
false.

  * •

When entering the third linker from a clause vertex, enter a linker
corresponding to a true literal.

Since $Q$ is true, at least one of that clause’s literals is true. As a
result, the vertex in a variable gadget that that linker connects to the
clause vertex is still present. So, Left has at least $8m+5$ moves remaining
at the end of Phase II. Meanwhile, Right has exactly $8m+4$ moves remaining,
as he begins Phase III on the third vertex in the escape path. Therefore, Left
wins, as required.

Now, suppose $Q$ is false. Then, there is some setting of the variables
$x_{2},x_{4},\ldots,x_{n}$ so that the formula is false regardless of the
values of $x_{1},x_{3},\ldots,x_{n-1}$. Take such a setting, and, as Right,
adopt the following strategy:

  * •

When moving from the top vertex of the diamond for $x_{i}$, move left if
$x_{i}$ should be set to true, and move right if $x_{i}$ should be set to
false.

  * •

For some $j$ such that clause $c_{j}$ is false, traverse the clause selection
gadget along the $j^{th}$ clause deletion path.

Around the end of the game, Left moves to the vertex for $c_{j}$. Since
$c_{j}$ is false, all of that clause’s literals are false. This means that
Left has at most $8m+4$ moves available in Phase III, since each linker from
$c_{j}$ no longer connects to a variable gadget. Right has exactly $8m+4$
moves remaining, and Left moves first. Therefore, Right wins, as required.

What remains to show is that neither player can do better if they deviate from
proper play. Each player has several ways in which they can deviate. A common,
silly deviation that either player can do at essentially any time is to delete
the vertex they would otherwise move to next. Usually, this causes that player
to be trapped after one more move. So, we ignore that possibility if it would
immediately trap them, and we analyze each other possible deviation.. A key
observation is that due to the long length of the win path, any player
entering its first vertex definitely wins the game. In each item that follows,
suppose that it represents the first deviation by either player in the whole
game.

A variable diamond player deviates in Phase I:

Any deviation by the variable diamond player (deleting the wrong vertex,
moving into a linker, backtracking after deleting a linker vertex) either
results in the diamond player immediately being trapped or delays that
player’s arrival at the bottom vertex of the variable diamond. This allows the
path player to reach the fifth vertex of the path and subsequently enter the
win path. None of the diamond player’s deviations can prevent this victory by
the path player.

Right does not move properly in Phase II:

(This case refers to move deviation, not deletion deviations.) Left reaches
prize in $m+8$ moves and subsequently enters the win path and wins, unless
Right can delete prize fast enough or if he can otherwise enter the win path
sooner. Since the game is in Phase II and the win path was connected only to
the fifth vertices of the variable paths and to prize, the only remaining
entry point to the win path is through prize. First, observe that the bottom
of the clause selection gadget cannot be reached any faster than $m+4$ moves.
Since the clause deletion paths always allow deletion of clauses in ascending
order, moving through a clause to jump from one clause deletion path to
another can only allow advancing one extra move along that path (at the cost
of two moves). Furthermore, the linkers are long enough that they cannot be
used to shortcut travel past a large number of clauses. The other way Right
could try to race Left to the win path is by traveling to $c_{1}$ in, say, the
last clause deletion path and then through a clause connector and into the
delay path. To reach the delay vertex adjacent to prize would take $m+7$
moves: three into the clause deletion path, one to $c_{1}$, $m$ through the
clause connector, and three through the delay path. But, it takes Left $m+7$
moves in Phase II to reach that same delay vertex, and Left moves first in
Phase II. Therefore, this deviation by Right allows Left to reach prize and,
hence, the win path.

Right does not delete properly in Phase II:

We have just seen that Right must move properly, so Right should never delete
the vertex they would otherwise move to. The only nontrivial way Right can
deviate is by making a regular move along a clause deletion path instead of
deleting a clause vertex. Left can still play Phase III properly, but she
might now also have additional moves available. Therefore, this deviation by
Right cannot cause him to win an otherwise lost game.

Left deletes prize:

This deviation does not affect the outcome of the game. At the point when Left
is able to delete prize at the end of Phase II, Right is on the second escape
vertex with all of his remaining moves forced. Left’s only sensible subsequent
move is to continue to move along the delay path, and from there no incentive
exists to deviate again.

Left deviates in Phase III:

Since Left is the only player who can make meaningful choices in Phase III, it
suffices only to show that Left cannot win a game where $Q$ is false. In other
words, we must show that Left can make no more than $8m+4$ moves in Phase III
if $Q$ is false. Here are all of the nontrivial ways Left can deviate:

Skipping one or more clause connector stalls:

Each clause connector skipped in the clause connector stalling stage reduces
Left’s total number of moves available by two, so shortening this stage cannot
be beneficial.

Intermingling/reordering the later stalling phases:

Left can perform the linker stalling sequences and the clause deletion path
stalling sequences in whatever order she pleases without increasing or
decreasing the total number of moves.

Doing a third linker stall and ending up in a clause deletion path:

First of all, this requires replacing a clause deletion path stalling sequence
(four moves) with a linker stalling sequence (two moves). Then, there are at
most $m+3$ moves available in the clause deletion path (including the move
used to enter it), since that is the number of vertices in a clause deletion
path. Since there are also $m+3$ vertices in a linker, this reduces Left’s
total moves available by at least two.

This completes the reduction showing that $\text{{tqbf}}\leq_{p}\textsc{upf}$.
Therefore, upf is pspace-hard, and, hence, pspace-complete, as required. ∎

##  5 Undirected Impartial Geography

The game uir is known in the literature as undirected geography or as
undirected vertex geography, and it is known to be in p [fsugeog]. The
N-positions are those position where the token is on a vertex that is
saturated by (i.e. included in) every maximum-size matching of the underlying
graph, a condition which can be checked in polynomial time. Left wins by
moving along an edge of some maximum-size matching. If the vertex with the
token is not saturated by some maximum-size matching, then the position is a
P-position, as every one of that vertex’s neighbors must be saturated by every
maximum-size matching excluding that vertex. We claim that, when played on a
bipartite graph, the game uif has the same N and P-positions, and Left can use
the same strategy to win as in uir. Our proof depends on the known strategy
for uir.

######  Theorem 5.

The game uif is in p when the underlying graph is bipartite. In particular, a
position is an N-position if and only if the vertex with the token is
saturated by every maximum-size matching of the underlying graph, and Left can
win from an N-position by moving regularly along an edge of some maximum-size
matching.

We use the following lemma:

######  Lemma 1.

Let $G$ be a graph, and let $M_{1}$ and $M_{2}$ be matchings in $G$ each with
the maximum possible number of edges. Each connected component of $M_{1}\cup
M_{2}$ has an even number of edges and is either a path or a cycle.

###### Proof.

The fact that each component is a path or cycle follows from the fact that
$M_{1}$ and $M_{2}$ are matchings, meaning every vertex in $M_{1}\cup M_{2}$
has degree at most $2$. It immediately follows that any cycle must have an
even number of edges, as otherwise two edges in the same matching would be
incident. Now, suppose for a contradiction that a component $H$ of $M_{1}\cup
M_{2}$ is a path with an odd number of edges. This means that one of the
matchings (assume $M_{1}$ without loss of generality) has one more edge in $H$
than the other matching. Let $M=\left(M_{1}\cap
H\right)\cup\left(M_{2}\cap\left(G-H\right)\right)$. Note that $M$ is a
matching of $G$ consisting of all of the edges of $M_{2}$ except in $H$, where
it uses the edges of $M_{1}$. This means that $M$ contains more edges than
$M_{2}$, contradicting the maximality of $M_{2}$. Therefore, $H$ has an even
number of edges, as required. ∎

We now prove Theorem 5.

###### Proof.

Let $G$ be a bipartite graph, and let $v$ be the vertex of $G$ with the token
on it. Suppose for a contradiction that this is a P-position of uir but an
N-position of uif, meaning that a player can gain an advantage by moving
irregularly. Furthermore, suppose $G$ has the fewest vertices among all
bipartite graphs in positions where an irregular move can be beneficial. Note
that $G$ has at least three vertices, since the position with a single vertex
is a P-position in both uif and uir, and the positions with two vertices are
either P-positions in both games (two isolated vertices) or N-positions in
both games (a single edge).

Since the current position is a P-position for uir, we know that $v$ is not
saturated by some maximum-size matching $M_{1}$ of $G$. Note that every
neighbor of $v$ must be saturated by $M_{1}$, as otherwise the matching’s size
could be increased by matching $v$ with an unmatched neighbor. The minimality
property of $G$ means that the first move must involve deleting a vertex other
than $v$ and that the rest of the game can be played as if it were uir without
affecting the outcome. Let $w$ be the neighbor of $v$ that Left should move to
to win, and let $u$ be the neighbor of $w$ that Left should delete to win. The
position after the move $\left(v,w,u\right)$ is identical to the position
after the move $\left(u,w,u\right)$ if the token had started on $u$ instead of
$v$. Since this winning move is a legal and winning move in uir, it must be
the case that $u$ is saturated by every maximum-size matching of $G$ and that
$uw$ is an edge in at least one of these matchings. Let $M_{2}$ be such a
matching. Note that $v$ must be matched to some vertex $x$ in $M_{2}$, as
otherwise, $M_{2}-\left\\{uw\right\\}\cup\left\\{vw\right\\}$ would be a
matching of $G$ of the same size as $M_{2}$, excluding $u$.

Let $H=M_{1}\cup M_{2}$. Let $H_{v}$ denote the connected component of $H$
containing $v$, and let $H_{w}$ denote the component of $H$ containing $w$.
Since $uw\in M_{2}$, we have that $u\in H_{w}$ also. By Lemma 1, each of
$H_{v}$ and $H_{w}$ has an even number of edges and is either a path or a
cycle. In particular, $H_{v}$ must be a path with $v$ at one end, since
$M_{1}$ excludes $v$. There are two cases to consider:

$H_{v}\neq H_{w}$:

Let $M=\left(M_{1}\cap
H_{v}\right)\cup\left(M_{2}\cap\left(G-H_{v}\right)\right)$. This is a
matching of $G$ consisting of all of the edges of $M_{2}$ except in $H_{v}$,
where it uses the edges of $M_{1}$. This means that $M$ has the same number of
edges as $M_{2}$, so it is a maximum-size matching that excludes $v$ and
includes $uw$, a contradiction.

$H_{v}=H_{w}$:

Since $uw\in M_{2}$, $H_{v}$ must consist of a path from $v$ to either $w$ or
$u$ not through the other, then the edge $uw$, then at least one additional
edge $wy$ (since $w$, a neighbor of $v$, is matched in $M_{1}$ and $u$ is
saturated by every maximum-size matching, including $M_{1}$).

Suppose first that $w$ is encountered before $u$ when traveling from $v$ along
$H_{v}$. Then, there is some edge $ut\in M_{1}$ incident to $u$. The path $P$
in $H_{v}$ from $v$ to $w$ has an even number of edges. Then, since $v$ and
$w$ are neighbors in $G$, the cycle $C=P\cup\left\\{vw\right\\}$ has odd
length, contradicting the fact that $G$ is bipartite.

Now, suppose that $u$ is encountered before $w$ when traveling from $v$ along
$H_{v}$. Let $P$ denote the path in $H_{v}$ from $v$ to $u$, and let $Q$
denote the path in $H_{v}$ from $w$ to the other endpoint of $H_{v}$. Note
that $P$ has an even number of edges and $Q$ has an odd number of edges,
containing one more edge of $M_{1}$ than $M_{2}$. Let $M=\left(M_{2}\cap
P\right)\cup\left(M_{1}\cap
Q\right)\cup\left(M_{1}\cap\left(G-H_{v}\right)\right)$. This is a matching of
the same size as $M_{1}$ that excludes $u$, a contradiction.

Therefore, $G$ cannot exist, and no advantage can be gained in uif on a
bipartite graph by moving irregularly, as required. ∎

Theorem 5 is false if the bipartite condition is dropped. Only one sub-case of
the proof depends on the graph being bipartite, but it is possible to
construct counterexamples based on that case. The smallest non-bipartite
counterexample, with five vertices and five edges, is depicted in Figure 13.
If the token begins on the vertex $v$ in the figure, the resulting position is
a P-position for uir and an N-position for uif. This graph has four maximum
size matchings (two edges each). Three of them consist of $ut$ and an edge of
the triangle; the fourth matching is $\left\\{uw,vx\right\\}$. Note that $u$
is saturated by every one of these matchings, but $v$ is excluded by the
matching $\left\\{ut,xw\right\\}$. Since $v$ is saturated by every maximum-
size matching that includes $uw$, we have that the depicted position is a
P-position in uir and an $N$-position in uif via the move
$\left(v,w,u\right)$.

$v,T$$x$$w$$u$$t$ Figure 13: Smallest counterexample to Theorem 5 on a non-
bipartite graph.

##  6 Undirected Impartial Geography with Stacking

As discussed in Section 5, the game $\text{{uir}}_{1}$ is in p. As a
consequence of Proposition 4, the game $\text{{uir}}_{2}$ is also known to be
in p. We now show that the game $\text{{uir}}_{4}$ is pspace-complete, even on
bipartite graphs with maximum degree at most $3$. Unlike our other reductions,
we reduce from geography rather than from tqbf.

######  Theorem 6.

The game $\text{{uir}}_{4}$ is pspace-complete, even when restricted to
bipartite graphs with maximum degree at most $3$.

We use the following lemma:

######  Lemma 2.

Consider the game of $\text{{uir}}_{4}$ played on a path of five vertices
$v_{1}$, $v_{2}$, $v_{3}$, $v_{4}$, and $v_{5}$ with initial heights $2$, $4$,
$3$, $1$, and $1$ respectively with the token starting on $v_{1}$ (see Figure
14). Modify the game so that it is a draw if the token reaches $v_{5}$ with
Left to move. Then, under optimal play by both players, this game is a draw,
and the ending heights are one of the following sequences (listed from $v_{1}$
through $v_{5}$): $[1,2,1,0,1]$, $[1,1,0,0,1]$, or $[0,0,0,0,1]$.

$2T$$4$$3$$1$$1$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$ Figure 14: The game under
consideration in Lemma 2

###### Proof.

Note first that the underlying graph is bipartite, so it is always Left’s turn
if the token’s vertex has odd index and Right’s turn if the index is even. So,
if the token reaches $v_{5}$, it is always Left’s turn and hence a draw.

This game is small enough that it can be solved by brute force. The first four
moves are forced: to $v_{2}$, to $v_{3}$, to $v_{2}$, and to $v_{3}$. The
resulting position has heights $[1,2,2,1,1]$ and the token on $v_{3}$ with
Left to move. She can move to either $v_{2}$ or $v_{4}$, resulting in the
heights $[1,2,1,1,1]$ in either case.

Suppose first that Left moves to $v_{2}$ on the fifth move. Then, Right can
move to either $v_{1}$ or $v_{3}$, making all heights equal $1$ in the
process. If he moves to $v_{1}$, all remaining moves are forced, and the token
ends up on $v_{5}$ with heights $[0,0,0,0,1]$. If Right moves to $v_{3}$, left
loses immediately if she moves to $v_{2}$, so she moves to $v_{4}$, forcing
Right to move to $v_{5}$, drawing the game with heights $[1,1,0,0,1]$.

Now, suppose that Left moves to $v_{4}$ on the fifth move. Right can
immediately draw the game by moving to $v_{5}$, leading to heights
$[1,2,1,0,1]$. Right’s other possible move is to $v_{3}$, also leaving these
heights. This forces the rest of the game to proceed by Left moving to
$v_{2}$, Right to $v_{1}$, and Left back to $v_{2}$, at which point Right
loses as the heights are $[0,1,0,0,1]$. So, Right should draw the game on the
sixth move rather than play the losing move to $v_{3}$.

Figure 15 depicts the full game tree. A position is labeled $(L)$ if Left
wins, $(R)$ if Right wins, or $(D)$ if the position is a draw. ∎

$2T$$4$$3$$1$$1$$(D)$$1$$4T$$3$$1$$1$$(D)$$1$$3$$3T$$1$$1$$(D)$$1$$3T$$2$$1$$1$$(D)$$1$$2$$2T$$1$$1$$(D)$$1$$2T$$1$$1$$1$$(D)$$1T$$1$$1$$1$$1$$(D)$$1T$$1$$1$$1$$(D)$$1T$$1$$1$$(D)$$1T$$1$$(D)$$1T$$(D)$$1$$2$$1$$1T$$1$$(D)$$1$$2$$1T$$1$$(L)$$1$$2T$$1$$(L)$$1T$$1$$1$$(L)$$1T$$1$$(L)$$1$$2$$1$$1T$$(D)$$1$$1$$1T$$1$$1$$(D)$$1$$1T$$1$$1$$(R)$$1T$$1$$1$$(R)$$1$$1$$1T$$1$$(D)$$1$$1$$1T$$(D)$
Figure 15: The game tree analyzed in the proof of Lemma 2

We now prove Theorem 6.

###### Proof.

We proceed via a reduction from geography ($\text{{dir}}_{1}$) to
$\text{{uir}}_{4}$. Consider an instance of geography on underlying digraph
$G$ with the token on vertex $t$. We construct an instance of
$\text{{uir}}_{4}$ on graph $G^{\prime}$ as follows.

  * •

Each vertex $v$ in $G$ corresponds to five vertices $v_{1}$, $v_{2}$, $v_{3}$,
$v_{4}$, and $v_{5}$ in $G^{\prime}$. The initial heights of these vertices
are $2$, $4$, $3$, $1$, and $1$ respectively.

  * •

The token begins on vertex $t_{1}$.

  * •

For each arc $vw$ in $G$, there is an edge $v_{5}w_{1}$ in $G^{\prime}$.

See Figure 16 for an example of this construction.

$T$$\Longrightarrow$$2T$$4$$3$$1$$1$$2$$4$$3$$1$$1$$2$$4$$3$$1$$1$$2$$4$$3$$1$$1$$2$$4$$3$$1$$1$
Figure 16: $\text{{uir}}_{4}$ construction from a given geography instance

Refer to the set of five vertices in $G^{\prime}$ obtained from a vertex of
$G$ as an _meta-vertex._ Say that a meta-vertex is _pristine_ if no move has
been made from one vertex in the meta-vertex to another. We say that play of
this game proceeds _properly_ if the play obeys the following guiding
principles for as long as possible.

  * •

If the token is not on a vertex of the form $v_{5}$, then the token is moved
within the current meta-vertex in such a way that each player avoids losing.

  * •

If the token is on a vertex of the form $v_{5}$, then the token is moved to a
vertex of the form $w_{1}$ within a pristine meta-vertex.

We have the following claims, which would complete our reduction:

  * •

Any player making an improper move loses.

  * •

If the game progresses properly for as long as possible, then the winner of
the geography position is the same as the winner of the corresponding
$\text{{uir}}_{4}$ position.

We show first that any improper move leads to loss. First, we show that
neither player has an incentive to make a move from a vertex $v_{1}$ to a
vertex $w_{5}$. Without loss of generality, suppose that Left makes such a
move as the first improper move of the game. Since the vertex moved to has
height $1$, it cannot have been moved to previously. In other words, the move
is to a pristine meta-vertex. Then, Right can move from $w_{5}$ to $w_{4}$,
which results in the deletion of $w_{5}$. This forces Left’s next move to be
from $w_{4}$ to $w_{3}$, deleting $w_{4}$. Then, Right moves from $w_{3}$ to
$w_{2}$ decreasing the height of $w_{3}$ to $2$ and trapping Left on $w_{2}$,
which has height $4$. So, a player making an improper move of this type loses.

Now, consider the other possible type of improper move: a move from a vertex
$v_{5}$ to a vertex $w_{1}$ of a non-pristine meta-vertex. Without loss of
generality, suppose that Left makes such a move as the first improper move of
the game. We claim that the heights of $w_{1}$ through $w_{5}$ must be
$[1,2,1,0,1]$ or $[1,1,0,0,1]$. Since this meta-vertex is not pristine, play
must have properly proceeded through it previously. Since we know that all
moves previously made involving that meta-vertex started with the token on
$w_{1}$ and remained within the vertex until the token reached $w_{5}$ and
subsequently departed, play must have proceeded as if the game in Lemma 2 were
being played within that vertex. So, the final heights must be as described by
Lemma 2. Since the move from $v_{5}$ to $w_{1}$ is possible, it cannot be that
$w_{1}$ has height $0$, so the heights must be $[1,2,1,0,1]$ or $[1,1,0,0,1]$,
as required.

If the heights are $[1,1,0,0,1]$, Right immediately wins by moving from
$w_{1}$ to $w_{2}$. If the heights are $[1,2,1,0,1]$, Right can move to
$v_{2}$, then Left to $v_{3}$, then Right back to $v_{2}$, again trapping
Left. So, a player making an improper move of this type also loses.

Now, we know that both players are incentivized to move properly whenever
possible. By Lemma 2, if $G$ consists of a single vertex, Right wins both the
geography position and the $\text{{uir}}_{4}$ position, as a draw in the lemma
is a loss for Left in this situation. Now, suppose $G$ has at least two
vertices, and suppose inductively that the winners of the geography position
and the corresponding $\text{{uir}}_{4}$ position are the same for any
geography position with fewer vertices than $G$. Note that, as long as the
token remains in the meta-vertex of $G^{\prime}$ corresponding to $v$ in $G$,
it is always Left’s move when the token is on $v_{1}$ or $v_{5}$ because each
meta-vertex is bipartite. Since Left is never incentivized to move improperly,
play through the first meta-vertex proceeds according to Lemma 2, as the best
Left can hope for from the first meta-vertex is to progress to another meta-
vertex. (In other words, Left cannot win within the first meta-vertex.)
Consider the $\text{{uir}}_{4}$ position reached once Left makes a move from
$v_{5}$ to some vertex $w_{1}$. This position is the same as the
$\text{{uir}}_{4}$ position corresponding to the geography position resulting
from Left moving from $v$ to $w$ in $G$, except that vertices $v_{1}$,
$v_{2}$, and $v_{3}$ may still exist in $G^{\prime}$. Moving to $v_{1}$ later
would be an improper move, and hence losing, so the current position has the
same winner as the one in which the entire meta-vertex corresponding to $v$
has been deleted. By our minimality property, the winner of the current
position is the same as the winner of the geography position after Left moves
from $v$ to $w$ in $G$. Since Left can move to the meta-vertex for $w$ in
$G^{\prime}$ if and only if she can move to $w$ in $G$, the initial
$\text{{uir}}_{4}$ position has the same winner as the initial geography
position, as required.

This completes the reduction showing that
$\text{{geography}}\leq_{p}\text{$\text{{uir}}_{4}$}$. Therefore,
$\text{{uir}}_{4}$ is pspace-hard, and, hence, pspace-complete, as required.

Finally, we know that geography is still pspace-complete when restricted to
bipartite graphs of maximum in/out degree at most $2$ and maximum total degree
at most $3$. We claim that if $G$ has these properties, then $G^{\prime}$ is
bipartite with maximum degree at most $3$. First, suppose that $G$ has
bipartition $\left(A,B\right)$. We construct a bipartition
$\left(A^{\prime},B^{\prime}\right)$ of $G^{\prime}$ as follows: If $v\in A$,
then $v_{1},v_{3},v_{5}\in A^{\prime}$ and $v_{2},v_{4}\in B^{\prime}$, and
vice versa if $v\in B$. Second, each incoming arc to a vertex $v$ of $G$
translates to an edge of $G^{\prime}$ incident to $v_{1}$, and each outgoing
arc translates to an edge of $G^{\prime}$ incident to $v_{5}$. If the maximum
in/out degree of $G$ is at most $2$, then there are at most two such edges
incident to each of these. Since each of $v_{1}$ and $v_{5}$ is adjacent to
one additional vertex ($v_{2}$ or $v_{4}$), each of these vertices has degree
at most $3$. This means that $G^{\prime}$ has maximum degree at most $3$,
since vertices with indices $2$, $3$, or $4$ have degree $2$. ∎

##  7 Summary and Open Problems

Prior to this work, the complexities of only three of the games
$\text{{xyz}}_{1}$ were known (dir, dpr, and uir). We resolve the complexities
of four more of these games (upr, dif, dpf, and upf) and a restricted case of
the fifth (uif). An obvious open problem is to fully resolve the complexity of
uif. Furthermore, the complexity of each game except upf is known for
bipartite graphs. Also, in Section 6, we determine that $\text{{uir}}_{4}$ is
pspace-complete. Since we also know that $\text{{uir}}_{2}$ is in p, this
leaves open the complexity of the game $\text{{uir}}_{3}$.

As mentioned in the introduction, the geography variants studied in this paper
are motivated by the board game Santorini. Future developments could continue
to bridge the gap between geography and Santorini. Here are several more
variant rules that can be considered:

  * •

The underlying graph can be restricted to come from some additional families
closed under taking induced subgraphs. We have seen bipartite, planarity, and
degree restrictions. _Santorini_ is played on a grid (including diagonal
adjacencies), so another restriction worth studying is grids and their induced
subgraphs.

  * •

Santorini has a winning condition other than the opponent having no legal
move. In the language of our geography variants with stacked vertices, this
condition is equivalent to ending one’s move on a vertex of height $1$.
Introducing alternative winning conditions is an avenue for further study.

  * •

In Santorini, each player has two tokens, and the players choose each token’s
starting position in turn order prior to moving them. Adding additional tokens
or token-placement moves could theoretically affect the complexities of games.
Some work in this direction has been undertaken for other games in the
geography family [fsgeog].

  * •

In our proof of Theorem 6, we assign each vertex a starting height. The
position we construct could not have been obtained from an initial position
with all vertices having maximum height, which may be a desirable condition to
consider.

  * •

Throughout our work, we treat the maximum height as a fixed parameter, as the
length of the game has a polynomial dependence on the maximum height $k$, and
hence an exponential dependence on $\log k$, the number of bits needed to
represent $k$. This suggests that if maximum height is unrestricted, the game
is unlikely to be in pspace. The question then is, what is the complexity of
this unrestricted game?

## References