Resumen
The Hamiltonian cycle reconfiguration problem asks, given two Hamiltonian cycles ??0
C
0
and ????
C
t
of a graph G, whether there is a sequence of Hamiltonian cycles ??0,??1,?,????
C
0
,
C
1
,
?
,
C
t
such that ????
C
i
can be obtained from ????-1
C
i
-
1
by a switch for each i with 1=??=??
1
=
i
=
t
, where a switch is the replacement of a pair of edges ????
u
v
and ????
w
z
on a Hamiltonian cycle with the edges ????
u
w
and ????
v
z
of G, given that ????
u
w
and ????
v
z
did not appear on the cycle. We show that the Hamiltonian cycle reconfiguration problem is PSPACE-complete, settling an open question posed by Ito et al. (2011) and van den Heuvel (2013). 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.