Hamiltonian Cycle Reconfiguration in Even Staircase Grid Graphs
Mohammad Istiaq Uddin · Brock University Digital Repository (Brock University) · 2026
Reconfiguration problems study the transformation from one valid configuration to another valid configuration through a sequence of valid changes, while maintaining some specific constraints after each changes. In theoretical computer science, reconfiguration problems connect graph theory, algorithms, computational complexity, combinatorial optimization, etc. The problem of Hamiltonian cycle reconfiguration has been studied for various graph classes. And the valid changes are maintaining the Hamiltonicity after each intermediate steps. Some previous results show linear time reconfiguration algorithm for 1-complex Hamiltonian cycles in a rectangular grid graph or an L-shaped grid graph. In this thesis, we give an algorithm for a Hamiltonian cycle reconfiguration problem. The algorithm transforms any 1-complex Hamiltonian cycle to any other 1 complex Hamiltonian cycle in an even staircase grid graph using a linear number of local operations. We use flip and transpose as the operations, where the changes are local to the grid. We take input of both of the Hamiltonian cycle and we answer if the reconfiguration is possible or not. For each of the input cycle, our approach is to split the cycle into two or three subproblems using a splitting chord method. Then we reconfigure each of the subproblems into canonical Hamiltonian cycles, respectively. We merge the canonical Hamiltonian cycle, and reconfigure it into canonical cycle of the whole graph. We find canonical cycle for both the input cycles. Then we transform in between the canonical cycle for the staircase grid graph. We introduce a splitting chord method, that helps to split the graph into subproblems. We provide a linear time reconfiguration algorithm, that combines some other reconfiguration algorithms, where the operation are linear too. We also introduce efficient data structures for the input of the Hamiltonian cycles. In this thesis, we find a result for the reconfiguration of Hamiltonian cycles for one of the class of polygon grid graphs. We provide techniques that can be extended to more complex polygon reconfiguration problems.