Soptq

頂点被覆問題（Vertex Cover）の説明は以下の通りです：与えられた $<G,k>$ において、$G$ は無向グラフであり、グラフ中に $V$ という点集合が存在し、$\lvert V \rvert <= k$ かつ $V$ の各頂点が $G$ のすべての辺をカバーしているかどうかを問います。つまり、$G$ の各辺の始点または終点が $V$ の一つの点であるということです。以下の図を例にとると、$<A,B>$ は条件を満たす点集合です。なぜなら、グラフ中の 4 つの辺はすべて $<A,B>$ の少なくとも一つの点で接続されているからです。

NP 完全性を証明するために、まずは NP 問題であることを証明します。与えられた $G$ と $V$ に対して、$G$ の各辺を走査し、それが $V$ の一つの点と接続されているかどうかをチェックするだけで、$V$ の正当性を判定することができます。明らかにこのプロセスは多項式時間で完了するため、頂点被覆問題は NP 問題です。

次に、NP 困難問題であることを証明するために、3-SAT を頂点被覆問題に帰着します。3-SAT の形式は以下の通りです：

$\begin{cases} C = C_1 \cap C_2 \cap \cdots \cap C_n \\ C_i = x_a^i \cup x_b^i \cup x_c^i \end{cases}$

与えられた 3-SAT 式に対して、次の操作を行います：

1. 各クラスタ内の 3 つの変数を相互に接続します。
2. 異なるクラスタ間で矛盾する同じ変数を接続します。ここで矛盾するとは、異なるクラスタの同じ変数 $x_a^i$ と $x_a^j$ が存在し、$x_a^i$ が真であれば $x_a^j$ は偽であり、$x_a^i$ が偽であれば $x_a^j$ は真であることを意味します。

これにより、3-SAT ブール式をグラフに変換し、$k = 2n$、$n$ はブール式のクラスタ数となります。例を挙げると、以下のような 3-SAT ブール式があるとします：

$C=(x+y+z) \cdot (\overline{x}+\overline{y}+\overline{z}) \cdot (x+\overline{y}+z) \cdot (\overline{x}+y+\overline{z})$

上記のルールに従って $C_1$ に対して作成されたグラフは次のようになります：

さて、以下の 2 つの問題を証明しましょう：

（1）3-SAT 問題が解を持つ場合、変換後のグラフ $G$ でも頂点被覆問題に解が存在する。 3-SAT に解が存在するため、$C = 1$ です。したがって、この 3-SAT の各クラスタには少なくとも 1 つの変数が真である必要があります。頂点被覆問題の $V$ のメンバーとして、その変数以外の 2 つの変数を選び、合計で $2n$ 個のメンバーを得ることができます。各クラスタについて、変換後のグラフでは三角形が構成されているため、三角形の 3 つの頂点から 2 つの頂点を選ぶと、その三角形のすべての辺が含まれることになります。また、各変数について、異なるクラスタに属する矛盾する変数と接続されています。したがって、3-SAT 問題が解を持つ場合、対応する $G$ は $k = 2n$ を満たすことが必ずしも満たされるため、解が存在します。

（2）頂点被覆問題 $<G, k>$ が与えられた場合、変換後の 3-SAT 問題も解を持つ。 $<G,k>$ を上記のルールに従って逆にブール式に変換し、$G$ に属さない頂点に対応する変数を真に設定すると、3-SAT 問題は真となります。

以上より、3-SAT 問題を頂点被覆問題に帰着することができました。したがって、頂点被覆問題は NP 完全です。