# Finding Hamiltonian and Longest \((s,t)\)-Paths of \(C\)-Shaped Supergrid Graphs in Linear Time
## 4 The Longest \((s,t)\)-Paths in C-Shaped Supergrid Graphs
Based on Lemmas 8-10 and Lemmas 11-14, we present Algorithm 1 to solve the longest path problem on \(C\)-shaped supergrid graph. Let the input of Algorithm 1 be a \(C\)-shaped supergrid \(C(m,n;k,l;c,d)\) and vertices \(s,t\in V(C(m,n;k,l;c,d))\). In Algorithm 1, it needs to determine whether \((C(m,n;k,l;c,d),s,t)\) satisfies conditions (F1), (F3), (F7), (F8), or (F9). Clearly, it can be done in constant time. By Lemmas 8-10, \(HP(C(m,n;k,l;c,d),s,t)\) does exist if \((C(m,n;k,l;c,d),s,t)\) does not satisfy any of conditions (F1), (F3), (F7), (F8), and (F9). By the proofs of Lemmas 8-10, \(HP(C(m,n;k,l;c,d),s,t)\) can be constructed in \(O(|V(C(m,n;k,l;c,d))|)=O(mn-kl)=O(mn)\) time. Consider that \((C(m,n;k,l;c,d),s,t)\) satisfies conditions (F1), (F3), (F7), (F8), or (F9). By Theorem 5, \(HP(C(m,n;k,l;c,d),s,t)\) does not exist. By the proofs of [PERSON] 11-14, the longest \((s,t)\)-path can be constructed in \(O(|V(C(m,n;k,l;c,d))|)=O(mn-kl)=O(mn)\) time. Thus, Algorithm 1 runs in \(O(mn)\)-linear time. We finally conclude the following main result. ``` Input: A \(C\)-shaped supergrid graph \(C(m,n;k,l;c,d)\) with \(mn\geqslant 2\), and two distinct vertices \(s\) and \(t\) in \(C(m,n;k,l;c,d)\). Output: The longest \((s,t)\)-path. 1.if\(a(=m-k)=1\) and \((C(m,n;k,l;c,d),s,t)\) does not satisfy the forbidden conditions (F1), (F3), (F7), (F8), and (F9), then output\(HP(C(m,n;k,l;c,d),s,t)\) constructed from Lemma 8;
2.if\(a



**Theorem 6**. : _Given a \(C\)-shaped supergrid graph \(C(m,n;k,l;c,d)\) and its two distinct vertices \(s\) and \(t\), Algorithm 1 computes a longest \((s,t)\)-path in \(O(mn)\)-linear time._

Let \(G\) be a graph and let \(\eta=|V(G)|\). The _all-pairs longest path problem_ is to find the longest paths between all pairs of vertices in \(G\). The most obvious solution to the all-pairs longest path problem is to run a longest path algorithm \(\eta^{2}\) times since there are \((\frac{\eta}{2})=\frac{\eta(\eta-1)}{2}\) pairs of vertices. Let \(G=C(m,n;k,l;c,d)\). Then, \(\eta=mn-kl=O(mn)\). By calling Algorithm 1\(\eta^{2}\) times, the all-pairs longest path problem for \(C(m,n;k,l;c,d)\) can be solved. Thus, the following corollary holds true. **Corollary 1**. : _Given a \(C\)-shaped supergrid graph \(C(m,n;k,l;c,d)\), the all-pairs longest path problem can be solved in \(O(m^{3}n^{3})\) time by calling Algorithm 1\((mn-kl)^{2}\) times._

## 5 Conclusions

The Hamiltonian problems can be applied to many fields including computer science, biology, molecular science, etc. However, they are NP-complete for general graphs and supergrid graphs. The Hamiltonian path problem is a special case of the longest path problem, and hence the longest path problem is generally difficult. The time complexities of these problems for solid supergrid graphs are still unknown. In this paper, we study these problems on \(C\)-shaped supergrid graphs, which form a subclass of solid supergrid graphs. We first discover some Hamiltonian connected properties of rectangular supergrid graphs. We then prove \(C\)-shaped supergrid graphs to be Hamiltonian connected except in a few conditions. Finally, we presented a linear-time algorithm for finding a longest path in \(C\)-shaped supergrid graphs between any two given vertices. This result can be applied to find the longest path on \(C\)-like objects with a supergrid structure. It is well known that [PERSON]'s algorithm computes all-pairs shortest paths of a digraph. It is interesting to construct a modification of [PERSON]'s algorithm for solving the all-pairs longest path problem on \(C\)-shaped supergrid graphs in linear time. We will post it as an open problem for interested readers. In addition, Laplacian matrix is a matrix representation of a graph. Together with [PERSON]'s theorem, it can be used to calculate the number of spanning trees for a given graph. It is interesting to see whether there exists a modification of the above result such that it can compute the number of longest paths between two vertices in \(C\)-shaped supergrid graphs efficiently.