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. 將每一個簇中的三個變量相互連接。
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$ 作出的圖為：

現在，我們還是來證明兩個問題：

（1）若已知一個 3-SAT 問題有解，則其轉換後的圖 $G$ 在頂點覆蓋問題上也有解。因為我們有一個 3-SAT 有解，即 $C = 1$。那麼對於這個 3-SAT 中每一簇都至少有一個變量為真。我們取除這個變量外的另外兩個變量為頂點覆蓋問題中 $V$ 的成員，最後一共可以得到 $2n$ 個成員。由於對於每一簇而言，轉換後在圖中構成了一個三角形，所以從三角形的 3 個頂點中選出兩個頂點必然會包含該三角形所有的邊。另一方面，對於每一個變量，其都有與其矛盾的不在一個簇的相同變量相連了。所以只要 3-SAT 問題有解，則對於每一個變量，不管其取值如何，都必然與與其相矛盾的相同變量連接（例如不管 $x$ 取真還是取假，都會與 $\overline{x}$ 相連）。所以 $G$ 在 $k = 2n$ 一定滿足，只要對應的 3-SAT 問題滿足。

（2）若已知一個頂點覆蓋問題 $<G, k>$，其轉換後的 3-SAT 也有解。 我們可以將 $<G,k>$ 通過上述規則逆向轉換為布爾表達式，且將 $G$ 中不屬於 $V$ 的頂點所對應的變量取真，則 3-SAT 問題為真。

綜上所述，我們將 3-SAT 問題歸約到了頂點覆蓋問題。所以頂點覆蓋問題是 NP 完全的。