Although, the Hamiltonicity of solid grid graphs are polynomial-time decidable, the complexity of the longest cycle problem in these graphs is still open. In this paper, by presenting a linear-time constant-factor approximation algorithm, we show that the longest cycle problem in solid grid graphs is in APX. More precisely, our algorithm finds a cycle of length at least $\frac{ 2n}{ 3}+1$ in 2-connected $n$-node solid grid graphs. Keywords: Longest cycle, Hamiltonian cycle, Approximation algorithm, Solid grid graph.
Categories: cs.DS cs.DM math.CO