algorithm - 「スパニング ツリー」を使用した Vertex-Cover 問題の 2 近似アルゴリズム

Question

Vertex-Cover 問題 (VC、既知の Np-Complete 問題) の 2 近似アルゴリズムに関する質問を見たことがありますが、答えがわかりません。問題は次のとおりです。「スパニング ツリー」を使用して、頂点カバー問題の 2 近似アルゴリズムを見つけます。さて、VC に関しては既に多くの貪欲なアプローチが提示されていますが、「スパニング ツリー」を使用した特殊なアルゴリズムは挑戦的です。何か案が？

Answer 1

指定されたグラフで最大一致を検索するだけで、解決策は最大一致を作成するノードのセットです。