頂点カバーから支配的なセットへの削減

Question

後者がNP-HARDであることを証明するために、頂点カバー（決定）問題を支配的なセット（決定）問題に縮小しようとしています。オンラインでいくつかの研究の後、私は多くの記事が頂点カバー問題の入力を各エッジに対して三角形を作成することによって、頂点カバー問題の入力を支配的なセット問題の入力に変換する縮小を使用することがわかりました。 ここはそのような記事の1つです（質問7を参照リンク）

私たちが支配的な設定問題への入力に分離された頂点を落とすと、その後、削減に対比階調を見つけることができます - 頂点カバーの問題への入力をグラフにすることができます。 $ n $ を含む絶縁型ノードとパラメータ $ k= n $ 。今、支配的なセットの問題への入力は、パラメータ $ k= n $ を持つ空のグラフです。さて、サイズ $ n $ の頂点カバーがあります。しかし、それは変換されたグラフの支配的なセットではありません（すなわち、頂点カバーの問題に対する答えは、はいですが、支配的なセットカバーの問題に対する答えはNO）です。

どのように私は削減を解決できますか？誰かが私に助言してもらえますか？

Answer 1

正しく理解した場合、頂点カバーインスタンスのグラフ $ g=（v、e）$ の頂点が分離されている場合にのみ問題があります。この場合は、 $ g $ を関連するグラフ $ g '=（v \ cup \ {x、y）に変換できます。 2つの新しい頂点を追加することによって$}、e '）$ $ x $ と $ y $ $ x $ と $ y $ がエッジで接続されている $ x $ の間のエッジ、 $ v $ の頂点です。形式的には： $ E '= E \ CUP \ {（x、v）\ inv \ cup \ {y \} \} $ 。

$ g $ の場合vertex-cover $ c $ の $ k $ 、 $ g '$ は $ k + 1 $ 、すなわち $ c \ cup \ {x \} $ 。

$ g '$ の場合、vertex-cover $ c $ が $ k + 1 $ 、 $ g $ は、最大 $ k $ 。これは、 $ c \ setminus \ {x、y \} $ がのすべてのエッジをカバーする必要があることに注意することができます。 $ E $ 、およびその $（x、y）\ in e '$ の $ X $ と $ y $ は $ c $ 、つまり $ | c \ setminus \ {x、y \} |= | C | - | C \ CAP \ {x、y \} | \ le | C | - 1 \ le k $ 。

$ g '$ には孤立した頂点がありません。これでそれを安全にグラフに変換することができます $ H $ < （既知の削減を使用して）（既知の削減を使用して）。 このようにして、 $ g $ が $ k $ の頂点カバーを持っていることを示しています。 SPAN CLASS="math-container"> $ \ iff $ $ H $ は、 $ k + 1 $ 。