ハミルトン閉路

ハミルトン閉路 (Hamiltonian cycle) とはグラフの全ての頂点をちょうど一回ずつ訪れる閉路のことです (オイラー閉路 (Eulerian cycle) とは異なります。オイラー閉路は全ての辺をちょうど一回ずつ使う閉じた歩道であり、深さ優先探索を使って線形時間で簡単に見つけられます)。ここでは有向グラフに対するハミルトン閉路問題が NP 困難であることの証明を二つ示します。

頂点被覆からの帰着

ハミルトン閉路問題の NP 困難性の証明の一つ目は、判定バージョンの頂点被覆問題からの帰着を使うものです。この証明では与えられた無向グラフ \(G\) と整数 \(k\) から、有向グラフ \(H\) であって \(H\) にハミルトン閉路が存在するときに限って \(G\) に大きさ \(k\) の頂点被覆が存在するようなものを構成します。一つ前の帰着と同じように、出力のグラフ \(H\) はいくつかのガジェットからなり、それぞれのガジェットが入力のグラフ \(G\) と整数 \(k\) の特徴を反映します。

この帰着の完全な例を次の図に示します。

\(\textsc{VertexCover}\) から \(\textsc{HamiltonianCycle}\) への帰着
図 12.14. \(\textsc{VertexCover}\) から \(\textsc{HamiltonianCycle}\) への帰着

「\(G\) に大きさ \(k\) の頂点被覆がある \(\iff\) \(H\) にハミルトン閉路がある」の証明はいつも通り二つのステップからなります。

以上より、「\(G\) に大きさ \(k\) の頂点被覆がある \(\iff\) \(H\) にハミルトン閉路がある」が言えます。\(G\) から \(H\) への変換には最大でも \(O(n^{2})\) 時間しかかからないので、有向グラフに対するハミルトン閉路問題が NP 困難であることが分かります。

3SAT からの帰着

ハミルトン閉路問題の NP 困難性は 3SAT からの帰着を使っても示すことができます。与えられた 3CNF 式 \(\Phi\) が \(n\) 個の変数 \(x_{1}, x_{2}, \ldots, x_{n}\) と \(k\) 個の節 \(c_{1}, c_{2}, \ldots, c_{k}\) を持つとし、\(\Phi\) が充足可能なときに限ってハミルトン閉路を持つような有向グラフ \(H\) をこれから構築します。

\(H\) には \(\Phi\) の各変数に対応する変数ガジェットが含まれます。変数 \(x_{i}\) に対する変数ガジェットは \(2k\) 個の頂点 \((i,0), (i,1), \ldots, (i,2k)\) を持ち、任意の添え字 \(j\) について \((i, j-1) \rightarrow (i,j)\) および \((i, j) \rightarrow (i, j-1)\) という辺を持ちます。

さらに隣り合う変数ガジェットの最初と最後の頂点は辺で結ばれます。つまり任意の添え字 \(i\) について \[ \begin{aligned} (i, 0) & \rightarrow (i+1, 0) & (i, 2k) & \rightarrow (i+1, 0) \\ (i, 0) & \rightarrow (i+1, 2k) & (i, 2k) & \rightarrow (i+1, 2k) \end{aligned} \] という辺が存在します。加えて最初と最後の変数ガジェットは次の辺で結ばれます: \[ \begin{aligned} (n, 0) & \rightarrow (1, 0) & (n, 2k) & \rightarrow (1, 0) \\ (n, 0) & \rightarrow (1, 2k) & (n, 2k) & \rightarrow (1, 2k) \end{aligned} \]

こうして出来上がるグラフ \(G\) にはちょうど \(2^{n}\) 個のハミルトン路が含まれ、それぞれが \(\Phi\) の \(n\) 個の変数に対する異なる真偽値割り当てに対応します。具体的には、\(i\) 番目のガジェットを左から右にたどるなら \(x_{i} = \textsc{True}\) であり、右から左なら \(x_{i} = \textsc{False}\) です。次の図も参照してください:

左: \(G\) における変数ガジェット 右: \(a = b = d = \textsc{True}\), \(c = \textsc{False}\) という真偽値割り当てに対応する \(G\) のハミルトン閉路
図 12.16. 左: \(G\) における変数ガジェット 右: \(a = b = d = \textsc{True}\), \(c = \textsc{False}\) という真偽値割り当てに対応する \(G\) のハミルトン閉路

\(\Phi\) の各節 \(c_{j}\) に対応する節ガジェットを \(G\) に加えることで \(H\) を作ります。節 \(c_{j}\) に対応する節ガジェットには一つの頂点 \([j]\) が含まれ、\([j]\) と変数ガジェットの間には次の図に示すような 6 本の辺が存在します。つまり、\(c_{j}\) の正のリテラル \(x_{i}\) に対しては辺 \((i, 2j - 1) \rightarrow\) \([j] \rightarrow\) \((i, 2j)\)、\(c_{j}\) の負のリテラル \(\overline{x}_{j}\) に対しては \((i,2j) \rightarrow\) \([j] \rightarrow\) \((i, 2j - 1)\) です。

左: \(H\) に含まれる節ガジェット 右: \(a = b = d = \textsc{True}\), \(c = \textsc{False}\) という \(\Phi\) を充足させる真偽値割り当てに対応する \(H\) のハミルトン閉路
図 12.17. 左: \(H\) に含まれる節ガジェット 右: \(a = b = d = \textsc{True}\), \(c = \textsc{False}\) という \(\Phi\) を充足させる真偽値割り当てに対応する \(H\) のハミルトン閉路

節ガジェットの辺の構成から、\(G\) のハミルトン閉路が \(H\) のハミルトン閉路に拡張できるのは対応する真偽値割り当てが \(\Phi\) を充足させるときに限られることが言えます。しらみつぶしに場合分けをしていけば、「\(H\) がハミルトン閉路を持つ \(\iff\) \(\Phi\) が充足可能」が示せます。

論理式 \(\Phi\) を \(H\) に変換するには \(O(kn)\) の時間かかりますが、これは最大でも \(\Phi\) の全長の二次式です。よって有向グラフに対するハミルトン閉路問題が NP 困難であると結論できます。

変種と拡張

前述の帰着を少し変更すると、ハミルトン “路” 問題が NP 困難であることも示せます。ここで \(G\) のハミルトン路とはもちろん \(G\) の全ての頂点をちょうど一回ずつ通る単純路のことです。実は \(\textsc{HamiltonianCycle}\) と \(\textsc{HamiltonianPath}\) の間には多項式時間帰着が双方向に存在します。どちらの帰着も簡単なので、詳細は練習問題とします。

この節で説明した二つの帰着はどちらも有向グラフを扱っていますが、無向グラフに対するハミルトン閉路問題も NP 困難です。実は有向グラフに対するハミルトン閉路問題から無向グラフに対するハミルトン閉路問題への簡単な帰着が存在します。この帰着の詳細も楽しい練習問題とします。

最後に、悪名高き巡回セールスマン問題 (traveling salesman problem) は辺に重みの付いたグラフにおける最短のハミルトン閉路 (または路) を見つける問題と言えます。最短の閉路/路を見つけるのは閉路/路が存在するかを判定するよりも明らかに難しい ――辺の重みが全て \(1\) のグラフを考えてみてください!―― ので、巡回セールスマン問題も同じく NP 困難です。