graph-theory - 二部グラフの頂点パッキング

Question

無向グラフの各ノードを正の重みに関連付けます。頂点パッキング問題は、ノード間のエッジを持つ 2 つのノードが選択されないように、最大​​の重みの合計を持つノードのサブセットを見つけることです。

二部グラフの頂点パッキング問題を解決する最も効率的な方法は何ですか? ノード数が 2 倍の最大フロー問題として定式化できました。より効率的で、おそらく直接的なアプローチはありますか?

Answer 1

VP が頂点カバー問題の実行可能な解である場合、P は頂点パッキング問題の実行可能な解です。したがって、最大頂点パッキングは最小頂点カバーと同等です。最小頂点カバーは、二部グラフの最大マッチングと同等です。