TSP in Solid Grid Graphs
Grid Graph がsolidであるとは、格子点における
の補グラフの連結であるということである。
グリッドグラフ上でのハミルトンパス（もしくはサイクル）問題は、solidなグリッドグラフ（穴を含まない）なら多項式時間で解くことができるが、一般のグリッドグラフ上ではNP-hardである。
一般グリッドグラフ上のTSPが解けると、一般グリッドグラフ上のハミルトンパス問題が解けてしまうので一般グリッドグラフ上のTSPはNP-hard.
solid grid graphにおけるTSPは未解決
