ハミルトン閉路問題

与えられたグラフが有向グラフの場合は有向ハミルトン閉路問題、無向グラフの場合は無向ハミルトン閉路問題と呼ばれる。

ハミルトン閉路の「出発点に戻る（閉路である）」という条件を緩和し、全頂点を一度ずつ通る「路」の有無を問う問題は、ハミルトン路問題と呼ばれる。

また、無向ハミルトン閉路問題は、各辺に重み（距離）が付けられたグラフにおいて最小重量のハミルトン閉路を求める巡回セールスマン問題（TSP）の特殊ケース（すべての辺の重みが等しい場合）と見なすことができる。

ハミルトン路・閉路問題は、有向グラフおよび無向グラフのいずれにおいてもNP完全問題であることが、1972年にリチャード・カープによって証明された^[3]。

また、以下の特殊なグラフにおいても、NP完全性は維持される：

• 二部グラフ^[4]
• 最大次数が3の無向平面グラフ^[5]
• 入次数・出次数が共に2以下の有向平面グラフ^[6]
• 橋（グラフ理論）（英語版）のない無向平面3-正則二部グラフ
• 3-連結3-正則二部グラフ^[7]
• 格子グラフ（英語版）の部分グラフ^[8]
• 格子グラフの立方体部分グラフ^[9]

一方で、4-連結平面グラフや2-連結平面グラフなどについては、常にハミルトン閉路が存在することが証明されており、線形時間で解を求めるアルゴリズムが存在する^[10]。

この問題に対する効率的な多項式時間アルゴリズムは見つかっていないが、いくつかの計算手法が提案されている。

• 力まかせ探索: すべての可能性を総当りで検証する方法。頂点数nの時、O(n!)であり、非常に低速である。
• 動的計画法: 頂点の集合 S と終点 v を状態として保持することで、 O(n² 2ⁿ) の時間計算量で解くことができる^[11][12]。
• バックトラッキング: 探索木を構築し、ハミルトン路を形成できないことが判明した時点で枝刈りを行う。最大次数3のグラフに対しては O(1.251ⁿ) で解くことができる^[13]。

• モンテカルロ法: Anders Björklund（英語版）によって提案された包除原理を利用したアプローチ。特定の行列式を計算することで、任意のn頂点グラフに対して O(1.657ⁿ) で、二部グラフに対してはO (1.415 ⁿ )で判定が可能である^[14]。
• SATへの変換: NP完全性の性質を利用し、問題を3-SATなどの充足可能性問題に変換して、既存のSATソルバーで解くことができる。