グラフの彩色 (3SAT からの帰着)

グラフ \(G = (V,E)\) の真の \(\pmb{k}\)-彩色 (proper \(\pmb{k}\)-coloring) とは、各頂点に \(k\) 個ある色のどれかを割り当てる関数 \(C: V \rightarrow \lbrace 1, 2, \ldots, k \rbrace\) であって辺でつながれた任意の頂点に違う色が割り当てられるものを言います ("色" は適当なラベルであり、ここでは整数とします。電磁スペクトル、CMYK ベクトル、Pantone の色番号などは使いません)。グラフ彩色問題とは与えられたグラフを彩色するのに必要となる色の数の最小値を計算する問題です。

グラフ彩色問題が NP 困難であることを示すには、与えられたグラフは真の 3-彩色を持つかを判定する \(\textsc{3Color}\) 問題だけを考えれば十分です。これから \(\textsc{3Color}\) が NP 困難なことを \(\textsc{3SAT}\) からの帰着で示します (なぜ \(\textsc{3SAT}\) かというと、問題に \(3\) が含まれているからです。ふざけているのかと思うのかもしれませんが、私は真面目に言っています)。つまり 3CNF 式 \(\Phi\) が与えられたときに、\(\Phi\) が充足可能なときに限って 3-彩色可能となるグラフ \(G\) を作れば良いことになります:

ここでは出力のグラフ \(G\) をガジェット (gadget) ごとに作っていくという、帰着においてよく使われる戦略を使います。\(G\) の各ガジェットが、入力の式 \(\Phi\) が持つ様々な特徴を表します。帰着をガジェットに分解して考えることは既存の帰着を理解するのに有用なだけでなく、NP 困難性を証明するための新しい帰着を考えるときにも有用です1

今考えている論理式からグラフへの帰着は三つのガジェットからなります:

最終的に出来上がるグラフ \(G\) には、頂点 \(T\), \(F\), \(X\) そして各変数 \(a\) に対応する頂点 \(a\) および \(\overline{a}\) がちょうど一つずつ含まれます。例えば \((a ∨ b ∨ c)\ ∧\) \((b ∨ \overline{c}\ ∨\) \(\overline{d})\ ∧\) \((\overline{a} ∨ c ∨ d)\ ∧\) \((a ∨ \overline{b} ∨ \overline{d})\) という、以前に \(\textsc{MaxClique}\) を説明するときに使った論理式は次のグラフになります。図中の 3-彩色は式を充足させる真偽値割り当ての一つ \(a = b = \textsc{True}\), \(b = d = \textsc{False}\) に対応します。

充足可能な 3CNF 式から作られる 3-彩色可能なグラフ
図 12.12
充足可能な 3CNF 式から作られる 3-彩色可能なグラフ

こうして出来上がるグラフの正しさの証明はこれまでにほぼ終わっています。式が充足可能ならば、任意の真偽値割り当てに基づいてリテラルの頂点を彩色でき、さらに (どの節にも \(\textsc{True}\) と \(\textsc{False}\) が少なくとも一つ含まれることから) その彩色を全ての節ガジェットに対する彩色に拡張できます。逆にグラフが 3-彩色可能ならば彩色から変数に対する真偽値割り当てを作ることができ、その割り当ては各節の少なくとも一つのリテラルを \(\textsc{True}\) にするので、全体の式を充足させます。

したがって \(\textsc{3Color}\) は NP 困難です。\(\textsc{3Color}\) は一般的な彩色問題 (「彩色に必要な色は最低何色?」) の特殊ケースなので、この一般的な最適化問題も NP 困難です。


  1. 例えば以前に示した \(\textsc{CircuitSAT}\) から \(\textsc{SAT}\) への帰着では各ゲートを論理式における節に変換しましたが、この帰着では節が "ゲートガジェット" となります。また \(\textsc{3SAT}\) から \(\textsc{MaxIndSet}\) への帰着では、節ガジェット (三角形) と変数ガジェット (矛盾する辺の間の辺) という二つのガジェットが登場しました。[return]

広告