math - 支配集贪婪逼近最坏情况示例

Question

要找到无向图 G 的最小支配集，您可以使用如下贪婪算法:
从一个空集 D 开始。直到 D 是一个支配集，添加一个具有最大未覆盖邻居数的顶点 v。

该算法一般不会找到最优解，它是 ln(Delta)-近似。 (如果 Delta 是 G 中顶点的最大度数)

现在我正在寻找一个简单的例子，贪婪算法没有找到最优解。我发现的唯一一个是集合覆盖问题的相关实例。 (右图为http://en.wikipedia.org/wiki/Set_cover_problem#Greedy_algorithm)
将此转换为图形将导致最少 14 个顶点和许多边。

有谁知道一个小例子？

提前致谢

Answer 1

考虑下图:

贪心方法将选择 B，然后选择 D 和 G。同时，E 和 F 形成支配集。