部分和 (最小頂点被覆からの帰着)

次に NP 困難性を示す問題は二章で登場した \(\textsc{SubsetSum}\) です。この問題では正の整数の集合 \(X\) と整数 \(T\) が与えられ、\(X\) の部分集合で要素の和が \(T\) となるものが存在するかどうかを判定します。

ここでも \(\textsc{VertexCover}\) からの帰着を作ります。つまり任意の無向グラフ \(G\) と整数 \(k\) から整数の集合 \(X\) と整数 \(T\) を構築し、\(G\) に大きさ \(k\) の頂点被覆が存在するときに限って和が \(T\) の \(X\) の部分集合があるようにするということです。ここで説明する帰着には二種類のガジェットがあり、それぞれ \(G\) の頂点と辺に対応します。

\(G\) の辺に適当な順番で \(0\) から \(m-1\) の番号を振ります。こうしたとき \(X\) の要素は各辺 \(i\) に対する \(b_{i} := 4^{i}\) という整数と、各頂点 \(v\) に対する \[ a_{v} := 4^{m} + \sum_{i \in \Delta(v)} 4^{i} \] という整数です。ここで \(\Delta (v)\) は \(v\) を端点に持つ辺の集合を表します。

\(X\) の要素が \(m+1\) 桁の四進数で表されていると思うこともできます。つまり \(X\) に含まれる整数が表すのは \(m\) 桁目が \(1\) ならば頂点、\(0\) なら辺であり、\(i < m\) について \(i\) 桁目の \(1\) が辺 \(i\) または辺 \(i\) の端点を表します。

そしてターゲットとなる整数 \(T\) は次のように定めます: \[ T := k \cdot 4^{m} + \sum_{i=0}^{m-1} 2 \cdot 4^{i} \] それでは、この帰着が正しいことを示しましょう。

• \((\Rightarrow)\) \(G\) に大きさ \(k\) の頂点被覆があると仮定する。\(X_{C} \subseteq X\) を

  1. 大きさ \(k\) の頂点被覆に含まれる頂点 \(v\) に対する \(a_{v}\) を全て含み、

  2. 大きさ \(k\) の頂点被覆に含まれる頂点を端点のちょうど一方に持つ辺 \(i\) に対する \(b_{i}\) を全て含む

  ものとして定義する。このとき \(X_{C}\) に含まれる整数の和を四進法で書くと、最初の \(m\) 桁には全て \(2\) が並び、\(m\) 桁より上位の桁は \(k\) となる。つまり、\(X_{C}\) の和は \(T\) に等しい。

• \((\Leftarrow)\) \(X^{\prime} \subseteq X\) の和が \(T\) になると仮定する。このとき \[ \sum_{v \in V^{\prime}} a_{v} + \sum_{i \in E^{\prime}} b_{i} = T \] となる \(V^{\prime} \subseteq V\) と \(E^{\prime} \subseteq E\) を取ることができる。

  ここでも \(T\) を四進数で表したとする。\(X\) には \(i < m\) 桁が \(1\) の整数が三つしかないので、\(T\) を計算するときには最初の \(m\) 桁で繰り上がりは起きない。また各辺 \(b_{i}\) は \(i\) 桁目に \(1\) を持ち、\(T\) の \(i\) 桁目は \(2\) なことから、\(V^{\prime}\) には \(G\) の各辺の少なくとも一方の端点が含まれる。つまり、\(V^{\prime}\) は頂点被覆である。

  また \(4^{m}\) より大きいのは頂点に対応する整数だけであり、\(\lfloor T / 4^{m} \rfloor = k\) であることから、\(V^{\prime}\) の大きさは \(k\) 以下である (実際にはちょうど \(k\) であり、証明は難しくない)。

例えばグラフ \(G = (V,E)\) において \(V = \lbrace u,\) \(v,\) \(w,\) \(x \rbrace\) および \(E = \lbrace uv,\) \(uw,\) \(vw,\) \(vx,\) \(wx \rbrace\) だった場合、\(X\) の一例は次の通りです: \[ \begin{aligned} a_u & := 111000_4 = 1344 & b_{uv} & := 010000_4 = 256 \\ a_v & := 110110_4 = 1300 & b_{uw} & := 001000_4 = 64 \\ a_w & := 101101_4 = 1105 & b_{vw} & := 000100_4 = 16 \\ a_x & := 100011_4 = 1029 & b_{vx} & := 000010_4 = 4 \\ & & b_{wx} & := 000001_4 = 1 \end{aligned} \] 大きさ \(2\) の頂点被覆を探している場合には、ターゲットとなる整数は \(T = 222222_{4} \) \(= 2730\) となります。頂点被覆 \(\lbrace v,w \rbrace\) は \(\lbrace a_{v},\) \( a_{w},\) \( b_{uv},\) \( b_{uw},\) \( b_{vx},\) \(b_{wx} \rbrace\) という \(X\) の部分集合に対応し、その和は確かに \(1300+1105+\) \(256+64+4+1 =\) \(2730\) となります。

この帰着は明らかに多項式時間で実行できます。\(\textsc{VertexCover}\) が NP 困難であることは前に示したので、\(\textsc{SubsetSum}\) が NP 困難であることが分かります。

読者への注意！

ここで強調しておくべきことがあります。300 ページほど前、三章で示したアルゴリズムは \(\textsc{SubsetSum}\) を \(O(nT)\) 時間で解きます。これは多項式時間アルゴリズムなのでは？ つまり、ちょうど今 P=NP を証明したのでは？ あれ、私の百万ドルはどこ？

残念ながら、人生はそう簡単にはいきません。もちろん、このアルゴリズムの実行時間は \(n\) と \(T\) の多項式で抑えられています。しかし多項式時間アルゴリズムとなるためには、実行時間が入力を表現するのに必要となるビット数の多項式である必要があります。\(X\) の要素の値と \(T\) の値は入力ビット数に対して指数的に大きくなることができ、そもそもここで示した帰着では \(T\) の値が入力グラフの大きさに対して指数的に大きくなっています。このような入力 \(T\) に対して動的計画法のアルゴリズムを適用すると実行時間が指数的になるので、動的計画法のアルゴリズムは多項式時間アルゴリズムとは言えません。

このような特徴を持つアルゴリズムは擬多項式時間 (pseudo-polynomial time) で実行できると言い、そのような NP 困難問題は弱 NP 困難 (weakly NP-hard) であると言います。つまり弱 NP 困難な問題とは、入力が一進数 (表す数の個数だけ \(1\) を並べたもの) で表されると多項式時間で解けるものの、入力が二進数で表されると NP 困難となる問題です。

これに対して入力が一進数で表されたとしても NP 困難となる問題を、強 NP 困難 (strongly NP-hard) であると言います。例えば \(\textsc{TravelingSalesman}\) は強 NP 困難です。この問題は、入力を全ての辺の重みが \(1\) または \(2\) である完全グラフに限った場合でも NP 困難となります。