Nemesis, an Escape Game in Graphs

Given a graph with exits and a starting vertex $s$, we introduce a first reduction performed in two phases (Fig. 3). The first phase consists in duplicating the exits so that each exit has degree $1$. See for instance the transition from a) to b) in Fig. 3. This transformation simplifies the structure by avoiding spurious cycles passing through exits, and it preserves the outcome of the game.

The second transformation consists in removing from the graph all vertices such that, if the fugitive ever reaches one of them, he is inevitably doomed to lose. More precisely, we iteratively prune all regular vertices of degree $1$ or $2$ (except the starting vertex $s$), since such vertices act as traps for the fugitive. As these vertices never play any role in a winning strategy, this pruning phase does not change the outcome of the game.

This pruning can be implemented using a Breadth-first Search (BFS) initialized with the initial set of vertices to be removed. We also discard any connected component that does not contain $s$. Overall, this preprocessing runs in linear time.

From now on, we therefore assume that all input graphs have been previously simplified. Note that this simplification never increases the degree of any vertex.

A key structure guaranteeing a win for the fugitive is the notion of a binary escape tree.

Binary escape trees provide the fugitive with a simple winning strategy.

Square grids deserve special attention, as readers familiar with Conway’s Angel game may recognize in Nemesis a variant of the demon’s strategy [7, 13]. The set of regular vertices of our instance forms an $m\times n$ square grid. Each corner vertex is connected to two exits, while each other boundary vertex is connected to exactly one exit. The instance and the corresponding strategies are illustrated in Fig. 4.

It is easy to see that if the fugitive starts at a vertex at distance at least $6$ from the closest exit, then the Nemesis has a winning strategy by cutting the corner exits. Conversely, if the distance from the starting vertex to the boundary vertices is at most $5$, the fugitive has a winning strategy by reaching the boundary and then moving around the grid (we do not formally prove this claim).

An interesting feature of the grid is that when the starting vertex $s$ is at distance $5$ from the exits, the fugitive has a winning strategy, even though $s$ does not satisfy the tree condition. We now prove this claim by contradiction.

Assume that a binary escape tree is rooted at a vertex at distance at most $1$ from $s$. Then the distance from this root to the exits is at least $4$. This root has two children at distance at least $3$ from the exits, each being the root of an independent binary escape tree. Each of these two nodes in turn has two children at distance at least $2$ from the exits, again serving as roots of independent binary escape trees. At the next level, we therefore obtain $8$ nodes at distance at least $1$ from the exits, each being the root of a binary escape tree.

However, any binary escape tree that is not rooted at an exit must contain at least one vertex adjacent to two exits. Hence, this construction implies the existence of $8$ distinct vertices each adjacent to two exits. Since the grid contains only $4$ such vertices, we obtain a contradiction. Therefore, $s$ does not satisfy the tree condition.

For arbitrary graphs, the tree condition is sufficient but not necessary to guarantee a win for the fugitive. We now show that when the graph $G$ is either a tree or has maximum degree at most $3$ (after graph simplification), this condition is also necessary.

We do not directly reduce QSAT but rather the NP-complete problem Planar Monotone Rectilinear 3SAT [14], which we denote by PMR3SAT. A key feature of these 3SAT instances is that each clause is either all-positive (containing only non-negated literals) or all-negative (containing only negated literals). An important property of Planar Monotone Rectilinear 3SAT is that it admits a geometric representation by non-crossing line segments.

In this representation, Boolean variables appear as a sequence of axis parallel rectangles lying on the horizontal axis. Clauses correspond to axis parallel rectangles placed in the half-plane for all-negative clauses, and in $y>0$ for all-positive clauses. The participation of a variable in a clause is encoded by a vertical segment that connects the rectangle of the variable to that of the clause. An instance of PMR3SAT is shown in the upper part of Fig. 5. We do not rely on the fact that these segments are axis-parallel.

We present the reduction of an instance of PMR3SAT to an instance of Nemesis in a planar multigraph. Let $n$ be the number of variables and $m$ the number of clauses of the PMR3SAT instance. The construction can be followed in Fig. 5.

Each Boolean variable is represented by a cycle of size $4K$, where $K$ is a constant chosen larger than the maximum number of clauses in which any given variable appears (larger than $m$ is sufficient). Thus, the ordered list of the $n$ variables of the PMR3SAT instance is encoded by a sequence of cycles - one per variable - each connected to the next by an intermediate vertex.

The key idea of the reduction is that, when traveling from the leftmost start vertex $s$ to the rightmost regular vertex $r$, the fugitive must traverse each cycle on one side or the other, so that his path from $s$ to $r$ encodes an assignment of the $n$ variables. For this purpose, we introduce intermediate vertices $t_i$ (for true) and $f_i$ (for false) on the two sides of each cycle. For instance, a path from $s$ to $r$ passing through vertices $t_1$, $f_2$, $t_3$, $t_4$, $f_5$, $f_6$ corresponds to the assignment where $x_1$, $x_3$ and $x_4$ are true, and $x_2$, $x_5$ and $x_6$ are false.

Observe that, regardless of the choice of side for each variable, all $s$-$r$ paths passing through the variable cycles have length $2nK$ (in the figure, with $n=6$, this length is $12K$).

Since this central path is crucial to the reduction, we ensure that the Nemesis cannot destroy its structure: all its edges are given multiplicities that make them unbreakable. The same applies to the additional edges introduced below. Almost all edges are therefore unbreakable. The only edges whose multiplicities allow the Nemesis to delete them are those incident with exits. The main exit is connected to the rightmost regular vertex $r$, and we set the multiplicity of this edge to $2nK-m+1$. The remaining exits correspond to the clauses.

Each clause is represented by a vertex $c_i$ connected to an exit by an edge of multiplicity $L+1$, where $L$ is chosen larger than $2nK$. Each clause vertex $c_h$ is also connected to the cycles of its variables.

For an all-positive clause $x_i\vee x_j\vee x_k$, the vertex $c_h$ is linked to $t_i$, $t_j$, and $t_k$ by unbreakable paths of length $L$.

For an all-negative clause $\overline{x_i}\vee \overline{x_j}\vee \overline{x_k}$, the vertex $c_h$ is linked to $f_i$, $f_j$, and $f_k$ by unbreakable paths of length $L$.

The choice of $L$, which is larger than the distance from $s$ to $r$, guarantees that these clause paths cannot create shortcuts between $s$ and $r$.

We first consider the direct paths from $s$ to $r$. For each variable $x_i$, the path goes through either $t_i$ or $f_i$. Assume, without loss of generality, that the fugitive arrives at $t_i$. From there, he may attempt to use one of the corresponding clause paths to reach an exit. When the fugitive is at $t_i$, his distance to $c_h$ is $L$, and the initial multiplicity of the exit edge from $c_h$ is $L+1$. Thus, if this exit edge has not been attacked by the Nemesis at least once beforehand, the fugitive can reach the clause exit, since the Nemesis no longer has enough time to remove that edge.

This forces the Nemesis to anticipate: before the fugitive reaches $t_i$, he must traverse a path of length $K$. During these $K$ rounds, the Nemesis must attack the exit edges of all clauses connected to $t_i$. Reducing the multiplicity of each such exit edge by one is sufficient to make the corresponding clause exit harmless. This reduction is unavoidable, because otherwise the fugitive could escape through that exit. Consequently, for each clause reachable from the fugitive’s path, the Nemesis must spend one round reducing an exit edge’s multiplicity from $L+1$ to $L$.

We now show that when the PMR3SAT instance is satisfiable, the fugitive has a winning strategy by following the path corresponding to a satisfying assignment. Along this path, the vertices $t_i$ and $f_i$ visited by the fugitive are connected to all $m$ clauses. Hence, the Nemesis must spend $m$ rounds preventing escape through the clause exits. This leaves only $2nK-m$ rounds during the fugitive’s traversal from $s$ to $r$ (a path of length $2nK$) to destroy the main exit edge. Since its multiplicity is set to $2nK-m+1$, that edge still has multiplicity $1$ at the beginning of round $2nK-m+1$ (after the fugitive reaches $r$), allowing the fugitive to exit.

We now show that if the PMR3SAT instance is not satisfiable, then the fugitive cannot escape. In this case, the fugitive’s path from $s$ to $r$ visits at most $m-1$ clauses, so the Nemesis has enough free rounds to remove the main exit edge.

Could the fugitive take a better path? Using a clause path is not advantageous: if he travels from $t_i$ or $f_i$ to $c_h$, then at every round the Nemesis can reduce the multiplicity of that clause’s exit edge. The Nemesis has exactly enough time to finish removing the exit edge before the fugitive can traverse it. The fugitive must then return to the central path, during which the Nemesis has ample time to destroy the main exit and win.

Another possibility would be to backtrack within the variable cycles, but this would require the fugitive to visit some vertex twice. This cannot help: if the fugitive has a winning strategy at all, then he has one without loops (Remark 5).

Thus, regardless of the path chosen by the fugitive, he cannot reach an exit.

Let us check now that the reduction takes only a polynomial time. The number of vertices involved in the central path is lower than $4nK$ with $K\le m$. The clause paths require $3(L+1)m$ vertices with $L$ of the order of $2nK$. Then the total number of vertices is $O(m^2{n}^2)$. The Nemesis instance encoding the initial PMR3SAT intance is thus computed in polynomial time.

This completes the NP-hardness proof, showing Theorem 2.

To establish the PSPACE-hardness of Nemesis, we need to move from the previous reduction from 3SAT (or SAT in general) to a reduction from Quantified SAT (QSAT). This amounts to going from a formula $\phi$ with only existential quantifiers,

to a formula with alternating existential and universal quantifiers,

Variables quantified existentially are called existential, while the others are called universal.

The satisfiability of such a quantified formula can be viewed as a game between an existential player, who assigns values to the existential variables with the objective of satisfying the formula, and a universal adversary, who assigns values to the universal variables with the objective of preventing satisfaction. It is this game that we reduce to Nemesis in order to prove PSPACE-hardness.

We now consider the initial reduction of SAT presented in Section 4.1 and explain how to update it in order to reduce the QSAT game. The main idea is to give the Nemesis control on the fugitive’s path over every universal variable, thereby emulating the power of the universal player. To explain the construction, we use an electrical analogy.

A first idea is to introduce, on each path corresponding to a universal variable (the $true$ path and the $false$ path), an edge of multiplicity $1$ that the Nemesis can use as a fuse. However, this naive approach potentially gives the Nemesis the ability to destroy both parallel fuses, which would allow her to win regardless of the fugitive’s choices. Thus, while this idea provides useful intuition, it grants too much power to the Nemesis and must be refined. We therefore introduce a fuse on each path of the universal variables and complement it with two derivation paths. This construction yields the so-called electric gadget, illustrated in Fig. 6.

Let us now describe the gadget in its full details. The gadget consists of a fuse (an edge of multiplicity one) placed on each branch immediately after the first edge of the paths corresponding to a universal variable $x_i$. The two fuses connect the vertices $u_i$ and $v_i$ on the $true$ path, and vertices $\overline{u_i}$ and $\overline{v_i}$ on the $false$ path. We complete the electric gadget with two additional paths of length $2$: one from $\overline{u_i}$ to $v_i$, and the other from $u_i$ to $\overline{v_i}$. All edges on these two paths are unbreakable.

We now explain why this gadget gives the Nemesis control over the universal variable $x_i$. We first recall that, in the initial reduction from SAT to Nemesis, the race between the fugitive reaching the main exit and the Nemesis destroying the main exit edge is tight: if the fugitive loses even one single round, he is defeated. We return to the electric gadget and assume, without loss of generality, that the Nemesis has chosen the value of variable $x_i$ to be true, meaning that she intends to forbid the fugitive from passing through $f_i$. When the fugitive reaches the cycle corresponding to the variable $x_i$, his first move must go either to $u_i$ or to $\overline{u_i}$. We analyze both cases.

• $\mathrm{■}$

  The fugitive moves to $u_i$. In this case, the Nemesis does not destroy the fuse $u_i{v}_i$. The fugitive then has two possible moves. If he goes to $v_i$, he effectively sets $x_i=true$, as expected by the Nemesis. If, on the contrary, he moves toward $\overline{v_i}$, he reaches $\overline{v_i}$ one round later than he would have by taking the direct path through $\overline{u_i}$. Since arriving at the main exit on time is a tight condition, this detour necessarily leads to defeat. Returning backwards would also result in defeat. Hence, the fugitive has no viable option other than proceeding toward $t_i$, as dictated by the Nemesis.

• $\mathrm{■}$

  The fugitive moves to $\overline{u_i}$. Since the Nemesis has decided that the fugitive must go through $t_i$ rather than $f_i$, she immediately deletes the fuse between $\overline{u_i}$ and $\overline{v_i}$. The fugitive cannot turn back, as doing so would again condemn him. His only remaining option is to move to $v_i$, and thus toward $t_i$, as imposed by the Nemesis. This detour costs the fugitive one round, but the Nemesis has also spent one round deleting the fuse. These two rounds therefore cancel out, and, in terms of timing, the situation is equivalent to that in the original SAT reduction.

Another possible scenario is that the Nemesis deletes one or both fuses associated with variable $x_i$ before the fugitive reaches $u_i$ or $\overline{u_i}$. We now show that she cannot take advantage from such a strategy. By spending a round to delete at least one fuse prematurely, the Nemesis allows the fugitive to use either one of the unbreakable detours $u_i,\overline{v_i},f_i$ or $\overline{u_i},v_i,t_i$ without being condemned to lose. This gives the fugitive an advantage, making such a strategy suboptimal for the Nemesis.

This analysis shows that the electric gadget allows the Nemesis to choose whether the fugitive passes through $t_i$ or $f_i$, a choice that directly corresponds to the value of the universal variable $x_i$. This control comes at no net cost to the Nemesis. Of course, she may choose not to exercise this power, but refraining from doing so does not give her additional rounds to destroy the main exit edge. Any such restraint is therefore useless. The control granted by the electric gadget over the universal variable cannot be exploited elsewhere in the game.

We now prove the PSPACE-hardness of Nemesis for multigraphs. The construction of the graph of Nemesis encoding a QSAT instance proceeds in two steps. First, we build the graph corresponding to the reduction from the SAT formula, as presented in Section 4.1. Second, we add the electric gadget at the entries of all universal Boolean variables.

This modification increases the size of the variable cycles by increasing the value of $K$ by a constant factor, but it does not otherwise affect the behavior of the construction.

We explore both directions of the reduction.

($\Rightarrow$) Assume that the quantified formula is satisfiable. This means that, in the corresponding QSAT game, the existential player has a winning strategy that satisfies all $m$ clauses. If the fugitive follows the same choices along the variable gadgets, he enforces the Nemesis to spend one round for each of the $m$ clauses of the SAT formula in order to block the clause exits.

For universal variables, the Nemesis may force the fugitive to lose one round by means of the electric gadget; however, in each such situation, the Nemesis must also spend one round to delete a fuse. Consequently, these rounds compensate each other, and the Nemesis gains no advantage. It follows that the fugitive reaches vertex $r$ before the Nemesis has completed the destruction of the main exit edge. At that point, this edge still has multiplicity $1$, and the fugitive escapes and wins the game. In other words, the fugitive has a winning strategy.

($\Leftarrow$) Assume that the quantified formula is not satisfiable. Then, in the QSAT game, the universal player has a strategy that prevents the existential player from satisfying all clauses. By following an identical strategy, the Nemesis prevents the fugitive from being able to approach all $m$ clause exits: at least one clause is necessarily missed. This missing clause yields one additional round that the Nemesis can devote to destroying the main exit edge. As a consequence, when the fugitive completes his path from $s$ to $r$, the edge to the main exit is no longer passable. Therefore, the Nemesis necessarily wins the game. It means that the Nemesis has a winning strategy.

This completes the proof of PSPACE-hardness of Nemesis for multigraphs. To establish PSPACE-completeness, it remains to show that Nemesis belongs to PSPACE. Since Nemesis is a finite two-player game with perfect information, each game position can be encoded using polynomial space. Moreover, by Remark 5, if the fugitive has a winning strategy, then he has one that does not visit the same vertex twice. Therefore, it is sufficient to consider plays without repeated vertices, and the length of any play is bounded by the number of vertices of the graph. The winner of the game can thus be determined by a depth-first exploration of the game tree, evaluating positions recursively according to the current player. Although this procedure may require exponential time, it uses only polynomial space, which shows that Nemesis on multigraphs belongs to PSPACE.

Combining this result with the PSPACE-hardness, we conclude that Nemesis on multigraphs is PSPACE-complete.