從最大獨立集合減少到支配集合以證明支配集合是NP完全的

Question

我知道從頂點覆蓋減少到支配集合。

但是，我看到是否可以從最大獨立集問題直接減少到支配集問題，以證明後一個NP完全。

有誰知道這是否已經完成？我無法在網上找到任何東西。

我希望能找到像沿證明的東西線：

如果有一個支配集大小爲k - >還有一個最大獨立集大小爲k。

AND

如果有一個最大獨立集大小爲k的 - >然後有一個控制集大小爲k。

Answer 1

是的，你可以從最大獨立集問題直接減少到支配集問題 - 但不是那麼直接，你需要以下面的方式構造另一個圖。然後我們可以證明，如果新圖有一個與k有關的一定大小的支配集，那麼如果原始圖具有獨立的一組大小k。構造是多項式的。

給定圖G = (V, E)我們可以在E構造另一個圖表G' = (V', E')其中對於每個邊緣e_k = (v_i, v_j)，我們添加一個頂點v_{e_k}和兩個邊緣(v_i, v_{e_k})和(v_{e_k}, v_j)。

我們可以證明G有一個獨立的尺寸集合k iff G'具有支配尺寸集合|V|-k。

（=>）假設我是一個大小 - k獨立設置的G，然後V-I必須是G'一個大小 - (|V|-k)支配集。由於I中沒有連接頂點對，因此I中的每個頂點都連接到V-I中的某個頂點。此外，每個新添加的頂點也連接到V-I中的某些頂點。

（< =）假設D是一個大小 - (|V|-k)獨立設置的G'，那麼我們可以安全地假設在D所有頂點是在V（因爲如果D包含添加的頂點，我們可以通過與其相鄰的一個替換它頂點在V並且仍然具有相同大小的主導集合）。

我們要求V-D是G一個尺寸 - k獨立設置，並通過矛盾證明這一點：假設V-D是不是獨立的，包含一對頂點v_i和v_j和邊緣e_k = (v_i, v_j)是E的。然後，在G'中，增加的頂點v_{e_k}需要由v_i或v_j支配，即v_i和v_j中的至少一個在D中。矛盾。因此V-D是一個大小-k獨立設置在G。

結合這兩個方向，你得到你想要的。