The hamiltonian path graph is connected for simple s, t paths in rectangular grid graphs

Rahnuma Islam Nishat (), Venkatesh Srinivasan () and Sue Whitesides ()
Additional contact information
Rahnuma Islam Nishat: Brock University
Venkatesh Srinivasan: Santa Clara University
Sue Whitesides: University of Victoria

Journal of Combinatorial Optimization, 2024, vol. 48, issue 4, No 4, 48 pages

Abstract: Abstract An s, t Hamiltonian path P for an $$m \times n$$ m × n rectangular grid graph $$\mathbb {G}$$ G is a Hamiltonian path from the top-left corner s to the bottom-right corner t. We define an operation “square-switch” on s, t Hamiltonian paths P affecting only those edges of P that lie in some small (2 units by 2 units) square subgrid of $$\mathbb {G}$$ G . We prove that when applied to suitable locations, the result of the square-switch is another s, t Hamiltonian path. Then we use square-switch to achieve a reconfiguration result for a subfamily of s, t Hamiltonian paths we call simple paths, that has the minimum number of bends for each maximal internal subpath connecting any two vertices on the boundary of the grid graph. We give an algorithmic proof that the Hamiltonian path graph $$\mathcal {G}$$ G whose vertices represent simple paths is connected when edges arise from the square-switch operation: our algorithm reconfigures any given initial simple path P to any given target simple path $$P'$$ P ′ in $$\mathcal {O}$$ O ( $$ |P |$$ | P | ) time and $$\mathcal {O}$$ O ( $$ |P |$$ | P | ) space using at most $${5} |P |/ {4}$$ 5 | P | / 4 square-switches, where $$ |P |= m \times n$$ | P | = m × n is the number of vertices in the grid graph $$\mathbb {G}$$ G and hence in any Hamiltonian path P for $$\mathbb {G}$$ G . Thus the diameter of the simple path graph $$\mathcal {G}$$ G is at most 5mn/ 4 for the square-switch operation, which we show is asymptotically tight for this operation.

Keywords: Reconfiguration algorithm; Hamiltonian paths; Simple paths; Rectangular grid graphs; Optimal-time algorithm; Lower bound; Solution-space graph (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01207-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:48:y:2024:i:4:d:10.1007_s10878-024-01207-w

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01207-w

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().