Complexity of Hamiltonian cycle reconfiguration (Q2633261)

Summary: The Hamiltonian cycle reconfiguration problem asks, given two Hamiltonian cycles \( C_0\) and \( C_t\) of a graph \( G\), whether there is a sequence of Hamiltonian cycles \( C_0\), \( C_1, \dots, C_t\) such that \( C_i\) can be obtained from \( C_{i - 1}\) by a switch for each \( i\) with \( 1 \leq i \leq t\), where a switch is the replacement of a pair of edges \( uv\) and \( wz\) on a Hamiltonian cycle with the edges \( uw\) and \( vz\) of \( G\), given that \( uw\) and \( vz\) did not appear on the cycle. We show that the Hamiltonian cycle reconfiguration problem is PSPACE-complete, settling an open question posed by \textit{T. Ito} et al. [Theor. Comput. Sci. 412, No. 12--14, 1054--1065 (2011; Zbl 1207.68166)] and \textit{J. van den Heuvel} [Lond. Math. Soc. Lect. Note Ser. 409, 127--160 (2013; Zbl 1307.05005)]. More precisely, we show that the Hamiltonian cycle reconfiguration problem is PSPACE-complete for chordal bipartite graphs, strongly chordal split graphs, and bipartite graphs with maximum degree 6. Bipartite permutation graphs form a proper subclass of chordal bipartite graphs, and unit interval graphs form a proper subclass of strongly chordal graphs. On the positive side, we show that, for any two Hamiltonian cycles of a bipartite permutation graph and a unit interval graph, there is a sequence of switches transforming one cycle to the other, and such a sequence can be obtained in linear time.