The Hamiltonian Path Graph is Connected for Simple $s,t$ Paths in Rectangular Grid Graphs

A \emph{simple} $s,t$ path $P$ in a rectangular grid graph $\mathbb{G}$ is a Hamiltonian path from the top-left corner $s$ to the bottom-right corner $t$ such that each \emph{internal} subpath of $P$ with both endpoints $a$ and $b$ on the boundary of $\mathbb{G}$ has the minimum number of bends needed to travel from $a$ to $b$ (i.e., $0$, $1$, or $2$ bends, depending on whether $a$ and $b$ are on opposite, adjacent, or the same side of the bounding rectangle). Here, we show that $P$ can be reconfigured to any other simple $s,t$ path of $\mathbb{G}$ by \emph{switching $2\times 2$ squares}, where at most ${5}|\mathbb{G}|/{4}$ such operations are required. Furthermore, each \emph{square-switch} is done in $O(1)$ time and keeps the resulting path in the same family of simple $s,t$ paths. Our reconfiguration result proves that the \emph{Hamiltonian path graph} $\cal{G}$ for simple $s,t$ paths is connected and has diameter at most ${5}|\mathbb{G}|/{4}$ which is asymptotically tight.

No reviews yet.

No comments yet.