最大独立集合 (3SAT からの帰着)

これから考えるいくつかの問題において、入力は単純重み無し無向グラフ、出力は何らかの構造的な特徴を持つ部分グラフのうち最大または最小のものです。

\(G\) を任意のグラフとします。\(G\) の独立集合 (independent set) とは、\(G\) の頂点の集合でどの頂点の組の間にも辺が無いものを言います。最大独立集合問題、略して \(\textsc{MaxIndSet}\) は与えられたグラフに含まれる最大の独立集合の大きさを求める問題です。これから \(\textsc{MaxIndSet}\) が NP 困難であることを \(\textsc{3SAT}\) からの帰着を使って示します:

任意の 3CNF 式 \(\Phi\) が与えられたとき、次のようにしてグラフ \(G\) を構築します。\(\Phi\) に含まれる節の数を \(k\) とすると \(G\) には \(3k\) 個の頂点があり、それぞれが \(\Phi\) のリテラルに対応します。\(G\) の任意の二つの頂点の間に辺があるのは (1) 二つの頂点が同じ節にある、もしくは (2) 二つの頂点がある変数とその否定である、場合のみです。例えば \((a ∨ b ∨ c)\ ∧\) \((b ∨ \overline{c} ∨ \overline{d})\ ∧\) \( (\overline{a} ∨ c ∨ d)\ ∧\) \((a ∨ \overline{b} ∨ \overline{d})\) という式は次のグラフに変形されます:

4 つの節を持つ充足可能な 3CNF 式から作られるグラフ (独立集合の大きさは 4)
図 12.6. 4 つの節を持つ充足可能な 3CNF 式から作られるグラフ (独立集合の大きさは 4)

\(\Phi\) の節に含まれる三つのリテラルに対応する \(G\) の頂点は全て辺で結ばれて三角形を作るので、\(G\) の独立集合はグラフの各三角形につき最大でも一つしか頂点を含みません。よって \(G\) の最大独立集合の大きさは最大でも \(k\) です。これから 「\(G\) に大きさ \(k\) の独立集合が存在する」と「元の式 \(\Phi\) が充足可能である」が同値であることを示します。 “同値である” ことの証明の常として、証明は二つの部分からなります。

3CNF 式 \(\Phi\) のグラフ \(G\) への変換は、総当たりを使ったとしても多項式時間で行えます。よって \(\textsc{3SAT}\) の入力 \(\Phi\) をグラフ \(G\) に変換した上で \(G\) に含まれる最大独立集合の大きさと \(\Phi\) に含まれる節の数を比べるという方法を使えば、\(\textsc{MaxIndSet}\) を多項式時間で解けるときに \(\textsc{3SAT}\) を多項式時間で解くことができます。もしそうならば P=NP なので、何かがおかしいです! よって \(\textsc{MaxIndSet}\) は NP 困難だと結論できます。