# Complexity of Hamiltonian Cycle Reconfiguration
## 2 PSPACE-Completeness
### Nondeterministic Constraint Logic  
Let \(G\) be a \(3\)-regular graph with edge weights among \(\{1,\,2\}\). A vertex of \(G\) is an _AND vertex_ if exactly one incident edge has weight \(2\), and a vertex of \(G\) is an _OR vertex_ if all the incident edges have weight \(2\). A graph \(G\) is a _constraint graph_ if it consists of only AND vertices and OR vertices. An orientation \(F\) of \(G\) is _legal_ if for every vertex \(v\) of \(G\), the sum of weights of in-coming edges of\(v\) is at least 2. A _legal move_ from a legal orientation is the reversal of a single edge that results in another legal orientation. Figure 1 illustrates all the possible orientations of edges incident to an AND vertex. We can also verify that all the possible legal move of an incident edge of the AND vertex are those depicted by the arrows in Figure 1. Given a constraint graph \(G\) and two legal orientation \(F_{0}\) and \(F_{t}\) of \(G\), the _nondeterministic constraint logic problem_ asks whether there is a sequence of legal orientations \(F_{0},F_{1},\ldots,F_{t}\) such that \(F_{i}\) is obtained from \(F_{i-1}\) by a legal move for each \(i\) with \(1\leq i\leq t\). Such a sequence of legal orientations is called a _reconfiguration sequence_. The nondeterministic constraint logic problem is known to be PSPACE-complete even if the constraint graph is planar [11]. See [18] for more information on constraint logic. For convenience of the reduction, we define a problem slightly different from the nondeterministic constraint logic problem. Let \(G\) be a bipartite graph with bipartition \((A,B)\) such that every vertex of \(A\) has degree 3 and every vertex of \(B\) has degree 2 or 3. The graph \(G\) has edge weights among \(\{1,2\}\) such that for every vertex of \(A\), exactly one incident edge has weight 2. An orientation \(F\) of \(G\) is _legal_ if  
* for every vertex \(v\in A\), the sum of weights of in-coming edges of \(v\) is at least 2, and
* every vertex of \(B\) has one or two in-coming edges, but at most one vertex of \(B\) has two in-coming edges. A _legal move_ from a legal orientation is the reversal of a single edge that results in another legal orientation. Notice that, in the legal moves, the vertices of \(A\) behave in the same way as the AND vertices of the nondeterministic constraint logic problem, that is, as shown in Figure 1. Given such a bipartite graph \(G\) and two legal orientation \(F_{0}\) and \(F_{t}\) of \(G\), the problem \(\Pi\) asks whether there is a sequence of legal orientations \(F_{0},F_{1},\ldots,F_{t}\) such that \(F_{i}\) is obtained from \(F_{i-1}\) by a legal move for each \(i\) with \(1\leq i\leq t\). We further add a constraint to the instance of the problem \(\Pi\) so that every vertex of \(B\) has exactly one in-coming edge in \(F_{0}\) and \(F_{t}\). **Lemma 1**. : _The problem \(\Pi\) is PSPACE-complete._  
Figure 1: All the possible orientations of edges incident to an AND vertex, where (blue) thick arrows denote the edges with weight 2, and (red) thin arrows denote the edges with weight 1. Each dotted circle represents a possible orientation of the edges, and two circles are joined by an arrow if one is obtained from the other by reversing the direction of a single edge. Proof. : We can observe that the problem \(\Pi\) is in PSPACE ([8], Theorem 1). We thus show a polynomial-time reduction from the nondeterministic constraint logic problem. Let \((G,F_{0},F_{t})\) be an instance of the problem, that is, \(G\) is a constraint graph, consisting of AND vertices and OR vertices, and \(F_{0}\) and \(F_{t}\) are two legal orientations of \(G\). We construct an instance \((G^{\prime},F^{\prime}_{0},F^{\prime}_{t})\) of the problem \(\Pi\) such that \((G,F_{0},F_{t})\) is a yes-instance if and only if \((G^{\prime},F^{\prime}_{0},F^{\prime}_{t})\) is a yes-instance. Let \(G^{\prime\prime}\) be the bipartite graph obtained from \(G\) by replacing each edge \(uv\) with two edges \(uw\) and \(wv\) so that \(uw\) and \(wv\) have the same weight as \(uv\), where \(w\) is a newly added vertex.