# Complexity of Hamiltonian Cycle Reconfiguration
## 2 PSPACE-Completeness
### Reduction
(3) The remaining parts are uniquely determined, since any Hamiltonian cycle pass through all the edges on the ears. Figure 5b illustrates the Hamiltonian cycle constructed in this way from the legal orientation in Figure 5a. Recall that every vertex of \(B\) has exactly one in-coming edge in \(F_{0}\) and \(F_{t}\). This guarantees that \(C_{0}\) and \(C_{t}\) are Hamiltonian. This completes the construction of the instance \((H,C_{0},C_{t})\) of the Hamiltonian cycle reconfiguration problem. We remark two facts, which we use in the proof of the following lemma. First, we can see that \(C_{0}\) and \(C_{t}\) are associated with \(F_{0}\) and \(F_{t}\), respectively. Second, if every vertex of \(B\) has exactly one in-coming edge in a legal orientation \(F\), then for any two Hamiltonian cycles that are associated with \(F_{t}\), there is a reconfiguration sequence from one to the other, in which the switches occur only in edge gadgets. **Lemma 2**. : _The instance \((G,F_{0},F_{t})\) of the problem \(\Pi\) is a yes-instance if and only if \((H,C_{0},C_{t})\) of the Hamiltonian cycle reconfiguration problem is a yes-instance._  
Proof. : We first prove the if direction. Assume that there is a reconfiguration sequence \(C_{0},C_{1},\ldots,C_{t}\) from \(C_{0}\) to \(C_{t}\). Let \(F_{i}\) be the legal orientation of \(G\) associated with \(C_{i}\) (Recall that a Hamiltonian cycle \(C\) of \(H\) has exactly one legal orientation associated with \(C\)). Notice that \(F_{i}=F_{i+1}\) if and only if \(C_{i+1}\) is obtained from \(C_{i}\) by a switch occurred in an edge gadget. When \(F_{i}=F_{i+1}\) for some \(i\) with \(0\leq i<t\), we remove \(F_{i+1}\) from the sequence \(F_{0},F_{1},\ldots,F_{t}\) to obtain the reconfiguration sequence from \(F_{0}\) to \(F_{t}\). We next prove the only-if direction. Assume that there is a reconfiguration sequence \(F_{0},F_{1},\ldots,F_{t}\) from \(F_{0}\) to \(F_{t}\). Recall that, for any two Hamiltonian cycles that are associated with \(F_{t}\), there is a reconfiguration sequence from one to the other, since every vertex of \(B\) has exactly one in-coming edge in \(F_{t}\). Thus, it suffices to show that for each Hamiltonian cycle \(C_{i}\) with \(0\leq i<t\), there is a Hamiltonian cycle \(C_{i+1}\) together with a reconfiguration sequence from \(C_{i}\) to \(C_{i+1}\), where \(C_{i}\) and \(C_{i+1}\) are Hamiltonian cycles associated with \(F_{i}\) and \(F_{i+1}\), respectively. Suppose that \(F_{i+1}\) is obtained from \(F_{i}\) by reversing the direction of an edge \(a_{i}b_{i}\), where \(a_{i}\) and \(b_{i}\) are the vertices of \(A\) and \(B\), respectively. Figure 5: (**a**) a legal orientation of 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; (**b**) the Hamiltonian cycle obtained from the legal orientation in Figure 5a. We take the configuration \(S_{3}\) for the gadget for \(a_{2}\), since the edges of \(a_{2}\) are oriented as \(f_{3}\) in Figure 5a. Notice that, when we replace the configuration from \(S_{3}\) to \(S_{4}\), we have two cycles. A bipartite graph is _chordal bipartite_ if each cycle in the graph of length greater than 4 has a chord, that is, an edge joining two vertices that are not consecutive on the cycle. Let \(D\) be the vertices of the reduction graph \(H\) incident with two edges having ears. We construct a graph \(H^{\prime}\) from \(H\) by adding edges \(uv\) for all vertices \(u\in D\) and all vertices \(v\) of \(H\) that is in the color class different from \(u\) and is not an interior vertex of any ear. It is obvious that \(H^{\prime}\) is bipartite. Suppose that \(H^{\prime}\) has a chordless cycle \(Z\) of length greater than 4. Clearly, \(Z\) has no interior vertices of any ear. We also have that \(Z\) has no vertices in \(D\), for otherwise \(Z\) would have a chord.