一般的にという意味がよくわからないが、ハミルトン閉路問題は NP 完全。
これはグラフが相当制限されているが、それでも >>133 にあるように NP 完全。

証明は平面グラフのハミルトン閉路に帰着して行う。ただし、それほど簡単ではない。