ハミルトン閉路問題（Hamiltonian Cycle Problem）とは、与えられたグラフにおいて、すべての頂点を一度だけ通って出発点に戻る路（ハミルトン閉路）が存在するかどうかを判定する問題である。
名称は、1857年にこの問題を正十二面体上のパズル「ハミルトンの世界一周ゲーム(Icosian Game)」として考案した数学者ウィリアム・ローワン・ハミルトンに由来する。
概要 与えられたグラフが有向グラフの場合は有向ハミルトン閉路問題、無向グラフの場合は無向ハミルトン閉路問題と呼ばれる。
ハミルトン閉路の「出発点に戻る（閉路である）」という条件を緩和し、全頂点を一度ずつ通る「路」の有無を問う問題は、ハミルトン路問題と呼ばれる。
また、無向ハミルトン閉路問題は、各辺に重み（距離）が付けられたグラフにおいて最小重量のハミルトン閉路を求める巡回セールスマン問題（TSP）の特殊ケース（すべての辺の重みが等しい場合）と見なすことができる。 計算複雑性 ハミルトン路・閉路問題は、有向グラフおよび無向グラフのいずれにおいてもNP完全問題であることが、1972年にリチャード・カープによって証明された。
また、以下の特殊なグラフにおいても、NP完全性は維持される： 二部グラフ 最大次数が3の無向平面グラフ. 入次数・出次数が共に2以下の有向平面グラフ. のない無向平面3-正則二部グラフ 3-連結3-正則二部グラフ. の部分グラフ. 格子グラフの立方体部分グラフ 一方で、4-連結平面グラフや2-連結平面グラフなどについては、常にハミルトン閉路が存在することが証明されており、線形時間で解を求めるアルゴリズムが存在する。 アルゴリズム この問題に対する効率的な多項式時間アルゴリズムは見つかっていないが、いくつかの計算手法が提案されている。
力まかせ探索: すべての可能性を総当りで検証する方法。頂点数nの時、O(n!)であり、非常に低速である。 動的計画法: 頂点の集合 S と終点 v を状態として保持することで、 O(n2 2n) の時間計算量で解くことができる。 バックトラッキング: 探索木を構築し、ハミルトン路を形成できないことが判明した時点で枝刈りを行う。最大次数3のグラフに対しては O(1.251n) で解くことができる。
モンテカルロ法: によって提案された包除原理を利用したアプローチ。特定の行列式を計算することで、任意のn頂点グラフに対して O(1.657n) で、二部グラフに対してはO (1.415 n )で判定が可能である。 SATへの変換: NP完全性の性質を利用し、問題を3-SATなどの充足可能性問題に変換して、既存のSATソルバーで解くことができる。
応用例 Network-on-Chip(NoC)
コンピュータの主要な機能を単一のマイクロチップに統合したシステム・オン・チップ(SoC)内のデータ転送において、ハミルトン路に基づいたルーティングアルゴリズムが用いられる。これにより、通信のデッドロックやライブロックを回避し、効率的マルチキャスト(多地点配送)が可能になる。
コンピュータグラフィックス 3Dレンダリングにおいて、三角形メッシュを効率的に処理するために利用される。連続する三角形が面を共有するように順序付ける「ストリップ化」は、メッシュの双対グラフにおいてハミルトン路を見つけることに相当する。
脚注
関連項目 グラフ理論 P≠NP予想 巡回セールスマン問題