# Complexity of Hamiltonian Cycle Reconfiguration
## 2 PSPACE-Completeness
### Reduction  
Let \((G,F_{0},F_{t})\) be an instance of the problem \(\Pi\). In this section, we construct a reduction graph \(H\) together with two Hamiltonian cycles \(C_{0}\) and \(C_{t}\) such that there is a reconfiguration sequence from \(F_{0}\) to \(F_{t}\) if and only if there is a reconfiguration sequence from \(C_{0}\) to \(C_{t}\). That is, \((G,F_{0},F_{t})\) is a yes-instance if and only if \((H,C_{0},C_{t})\) is a yes-instance of the Hamiltonian cycle reconfiguration problem. We use three types of gadgets corresponding to the vertices in \(A\), the vertices in \(B\), and the edges of \(G\). A gadget for a vertex in \(A\) and a gadget for an edge of \(G\) is shown in Figure 2(a),b respectively. Double lines in the figures denote _edges with ears_, where an _ear_ of an edge \(uw\) is a path of length 3 joining \(u\) and \(w\). Recall that, in the legal moves, the vertices in \(A\) behave in the same way as the AND vertices. We thus refer to the gadgets for the vertices in \(A\) as AND gadgets. Let \(b\) be a vertex in \(B\) of degree \(k\), and recall that \(k\) is 2 or 3. A gadget for \(b\) is a cycle \((u_{0},w_{0},u_{1},w_{1},\ldots,u_{k-1},w_{k-1})\) of length \(2k\) such that the edge \(w_{i}u_{i+1}\) has a ear for each \(i\) with \(0\leq i<k\) (indices are modulo \(k\)). Figure 3: Gadgets. Double lines denote edges with ears. (**a**) an AND gadget; (**b**) an edge gadget. Figure 2: The reduction from the nondeterministic constraint logic problem to the problem \(\Pi\). White points denote the vertices of \(A\), and gray points denote the vertices of \(B\). Thick (blue) lines denote the edges with weight 2, and thin (red) lines denote the edges with weight 1. We construct the reduction graph \(H\) from \(G\) as follows: (1) Let \(a\) be a vertex in \(A\), and let \(e_{l},e_{r},e_{d}\) be the edges of \(G\) incident to \(a\) such that \(e_{l}\) and \(e_{r}\) have weight \(1\) and \(e_{d}\) has weight \(2\). We identify the vertices \(l^{\prime}_{u}\) and \(l^{\prime}_{w}\) of the gadget for \(a\) with the vertices \(x_{u}\) and \(x_{w}\) of the gadget for \(e_{l}\), respectively. Similarly, we identify the vertices \(r^{\prime}_{u}\) and \(r^{\prime}_{w}\) of the gadget for \(a\) with the vertices \(x_{u}\) and \(x_{w}\) of the gadget for \(e_{r}\), respectively. Moreover, we identify the vertices \(d^{\prime}_{u}\) and \(d^{\prime}_{w}\) of the gadget for \(a\) with the vertices \(x_{u}\) and \(x_{w}\) of the gadget for \(e_{d}\), respectively. (2) Let \(b\) be a vertex in \(B\) of degree \(k\), and let \(e_{0},e_{1},\ldots,e_{k-1}\) be the edges of \(G\) incident to \(b\). We identify, for each \(i\) with \(0\leq i<k\), the vertices \(u_{i}\) and \(w_{i}\) of the gadget for \(b\) with the vertices \(y_{u}\) and \(y_{w}\) of the gadget for \(e_{i}\), respectively. (3) We finally concatenate the gadgets for the vertices in \(A\) cyclically using edges with ears joining the vertices \(c^{\prime}_{u}\) and \(c^{\prime}_{w}\) of the gadgets. Before describing the construction of the Hamiltonian cycles \(C_{0}\) and \(C_{t}\), we consider the possible configurations of a Hamiltonian cycle of the reduction graph \(H\) passing through the gadgets. We will show that all the possible configurations in an AND gadget and an edge gadget are shown in Figure 3(a,b), respectively. We can also verify that all the possible transformations of Hamiltonian cycles by a single switch occurred in a gadget are those depicted by the arrows in the figures. Let \(C\) be a Hamiltonian cycle. We first consider the configurations of \(C\) in an AND gadget. The Hamiltonian cycle \(C\) passes through all the edges on the ears, since interior vertices of an ear has degree \(2\). Thus, \(C\) passes through any of the edges \(c_{u}d_{w}\), \(c_{u}c_{w}\), \(c_{u}r_{w}\), or \(c_{u}l_{w}\). We also have that \(C\) does not pass through the edges \(l^{\prime}_{u}l^{\prime}_{w}\), \(r^{\prime}_{u}l^{\prime}_{w}  
arbitrarily among those in Figure 4b.