algorithm - 使用“生成树”的顶点覆盖问题的 2 近似算法

Question

我看过一个关于顶点覆盖问题（VC，已知 Np 完全问题）的 2 近似算法的问题，但我不知道答案。问题如下：使用“生成树”找到顶点覆盖问题的 2 近似算法。好吧，已经为 VC 提出了许多贪婪的方法，但是使用“生成树”的特殊算法具有挑战性。任何想法？

Answer 1

您只需在给定图中搜索最大匹配，解决方案就是创建最大匹配的节点集。