問題タブ [vertex-cover]

次の問題の削減を見つける必要があります。

Vertex Cover- 与えられた (G=(V, E), k)-> G は無向グラフであり、E のすべてのエッジをカバーするサイズ k の S (V のサブグループ) が必要です。

Hal Vertex Cover- 与えられた (G=(V', E'), k')-> G は無向グラフです。また、E' のエッジのちょうど半分をカバーするサイズ k' の S' (V' のサブグループ) が必要です。

その方法と、Karp-Reduction が真になる理由 (証明の 2 つの方向) を教えていただければ幸いです。

ありがとうございました。

二分探索木を使用するような最小の頂点カバーを見つけるアルゴリズムをいくつか見つけましたが、三分木を使用する方がさらに優れていることを読みました。しかし、私はそれについての情報を見つけることができず、そのためのアルゴリズムを考えることもできません.

誰かがそれを行う方法を知っていますか?

始めるのが難しいと感じている宿題の問題があります。扱いにくいことを示すために、Karp (シングル コール) 削減に取り組んでいます。この課題では、問題は意図的にあいまいです。ここの誰かがそれを知っているか、私が始めるのに役立つ解決策の例を提供できることを望んでいました.

問題は、提供されたコードでのみ説明されています。次のコンポーネントがあります。

B = (G, T, k) ここで、B は「Blah」問題のインスタンス、G = (V,E) はグラフ (重みなし、無向)、T は V の頂点のサブセット、k は整数。B の証明書は、G のサブグラフ S = (V', E') を返します。yes インスタンスの検証子も提供されます。

はいのインスタンス

この問題と Independent-Set または Vertex-Cover の問題との間にいくつかの類似点があります。これらは扱いにくいことを示すために還元するのに適した候補だと思いますが、まだ問題を十分に理解していません。この問題に関する議論がどこかにある場合、または誰かがいくつかの例を提供できる場合は、大いに感謝します。ありがとうございました！