頂点被覆問題のNP完全性 - 忘れても大丈夫

頂点被覆問題がNP完全であることを示します．頂点被覆問題のNP完全性から独立集合問題とクリーク問題がNP完全であることが導かれます．

頂点被覆問題・独立集合問題・クリーク問題

まず，頂点被覆問題，独立集合問題とクリーク問題の関係性について紹介します．

頂点被覆問題（vertex cover problem）
　入力：無向グラフ $G = (V, E)$ ，非負整数 $k$
　出力： $G$ の頂点被覆でサイズ $k$ 以下のものが存在するか

頂点部分集合 $C \subseteq V$ で，任意辺の $\{u, v\} \in E$ に対して $\{u, v\} \cap C \neq \emptyset$ を満たすものを $G$ の頂点被覆と呼ぶ

独立集合問題（independent set problem）
　入力：無向グラフ $G = (V, E)$ ，非負整数 $k$
　出力： $G$ の独立集合でサイズ $k$ 以上のものが存在するか

頂点部分集合 $I \subseteq V$ で， $I$ のどの2頂点も隣接していないものを $G$ の独立集合と呼ぶ

クリーク問題（clique problem）
　入力：無向グラフ $G = (V, E)$ ，非負整数 $k$
　出力： $G$ のクリークでサイズ $k$ 以上のものが存在するか

頂点部分集合 $C \subseteq V$ で， $C$ のどの2頂点も隣接しているものを $G$ のクリークと呼ぶ

これらの問題は無向グラフの頂点部分集合に対して定義されるもので，任意の無向グラフ $G$ に対して次が成り立ちます．
　・ $X$ が $G$ の頂点被覆
　・ $V \setminus X$ が $G$ の独立集合
　・ $V \setminus X$ が $G$ の補グラフ $\overline{G}$ のクリーク

ただし， $G$ の補グラフを $\overline{G} = (V, V^2 \setminus E)$ とします．
このことから，これらの中で少なくとも1つの問題がNP完全であることを示せば，残りの問題もNP完全であることが分かります（多項式時間帰着を上の通りに作る）．これらの問題はNP完全性ということに関しては似ている問題に見えますが， $k$ をパラメータとしたパラメータ化問題では異なるクラスに属する問題となります（頂点被覆問題が FPTで，独立集合問題とクリーク問題がW[1]-完全； Parameterized complexity - Wikipedia）．また，頂点被覆問題には2-近似多項式時間アルゴリズムが存在しますが，独立集合問題には P $\neq$ NP という仮定の下で定数近似多項式時間アルゴリズムが存在しないことが示されています．（構造として一見似ているものも多方面から詳細に調べると違うということが分かるのは良いですね．）

頂点被覆問題のNP完全性の証明

頂点被覆問題がクラスNPに属することは明らかです．なぜらなば頂点部分集合を証拠としてそれが頂点被覆であることと，サイズが $k$ 以下であることが多項式時間で検証できるからです．

次に，3SAT問題から頂点被覆問題への多項式時間帰着を示します．3SAT問題の入力を変数集合 $U = \{u_1, \ldots, u_n\}$ と節集合 $C = \{c_1, \ldots, c_m\}$ とします．3SAT問題 $(U, C)$ から頂点被覆問題の入力である無向グラフ $G = (V, E)$ を次のように構成します．
　・ $V = \left( \cup_{i = 1}^{n} V_i \right) \cup \left( \cup_{j = 1}^{m} V'_j \right)$ ，
　・ $E = \left(\cup_{i = 1}^{n} E_i \right) \cup \left(\cup_{j = 1}^{m} E'_j \right) \cup \left(\cup_{j = 1}^{m} E''_j \right)$
各 $V_i, V'_j, E_i, E'_j, E''_j$ は次のように構成します．
　・各変数 $u_i$ に対して， $V_i = \{u_i, \lnot{u_i}\},\, E_i = \{u_i \, \lnot{u_i} \}$
　・各節 $c_j$ に対して， $V'_j = \{a_{j1}, a_{j2}, a_{j3} \}$ ， $E'_j = \{a_{j1} a_{j2}, a_{j1} a_{j3}, a_{j2} a_{j3} \}$
　・各節 $c_j$ に含まれる変数をそれぞれ $x_j, y_j, z_j$ と表したときに， $E''_j = \{a_{j1} x_j,\, a_{j2} y_j,\, a_{j3} z_j \}$
このとき，この変換は $n$ と $m$ の多項式時間でできます．また， $k = n + 2m$ とします．
　　　　 f:id:tatanaideyo:20190110135135p:plain

次に，正当性を示します．すなわち，
　　3SAT $(U, C)$ が充足可能 $\Leftrightarrow$ $G$ のサイズ $k$ 以下の頂点被覆が存在
が成立つことを示します．

$\Rightarrow)$ 　3SAT $(U, C)$ は充足可能でその真理値割り当てを $t : U \rightarrow \{\top, \bot\}$ とします．このとき， $G$ の頂点部分集合 $S$ を各 $u_i$ に対して， $t(u_i) = \top$ ならば $u_i \in S$ ， $t(u_i) = \bot$ ならば $\lnot u_i \in S$ とします．これによって $E_i$ は被覆されます．また，各節 $\{x_j, y_j, z_j\} \in c_j$ に対して， $S$ に含まれない頂点を優先的に任意に2つ選びます．これを， $x_j, y_j$ とします．このとき， $a_{j1}, a_{j2} \in S$ とします．これによって， $E''_j$ と $\{a_{j1} x_j, a_{j2} y_j\} \in E'_j$ は被覆されます．また， $c_j$ は充足されているので $z_j \in S$ となり，したがって $\{a_{j3} z_j\} \in E'_j$ は被覆されます．このとき， $|S| = n + 2m$ ですべての辺が被覆されているので必要条件が成り立ちます．

$\Leftarrow)$ 　 $G$ のサイズ $k = n + 2m$ 以下の頂点被覆を $S$ とします．ここで， $G$ の任意の頂点被覆は $E_i$ を被覆するために $V_i$ から少なくとも1つの頂点を選ぶ必要があり， $E''_j$ を被覆するために少なくとも2つの頂点を選ぶ必要があるので，サイズは少なくとも $n + 2m$ 以上となります．したがって， $S$ のサイズはちょうど $n + 2m$ となります．
3SAT $(U, C)$ の真理値割り当て $t : U \to \{\top, \bot\}$ を， $u_i \in S$ ならば $t(u_i) = \top$ ， $\lnot u_i \in S$ ならば $t(u_i) = \bot$ とします． $V_i$ からはちょうど1つの頂点が $S$ に含まれるので正しい真理値割り当てとなります．また，各節 $\{x_j, y_j, z_j\} \in c_j$ に対して少なくとも1つの頂点が $S$ に含まれます．なぜならば， $S$ に含まれる $V'_j$ の頂点はちょうど2つで，もし $x_j, y_j, z_j$ が全て $S$ に含まれないとすると， $E''_j$ に被覆されない辺が存在してしまうからです．

参考文献

Michael R. Garey and David S. Johnson: COMPUTERS AND INTRACTABILITY A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979, pp. 53--56.

証明が思いついたので良かった!! Garey と Johnson のガジェットがキレイだったので参照してます．